#include <bits/stdc++.h>

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

const int mod = 666013;
int a[100005];
int n, k, m;
vector<pair<long long, long long>> Q[100005];
int last[100005];
long long sum;
long long sol[100005];
long long aint[4 * 100005];

int Leftson(int node)
{
    return 2 * node;
}
int Rightson(int node)
{
    return 2 * node + 1;
}

void Update(int node, int left, int right, int poz, int val)
{
    if(left == right)
    {
        aint[node] = val;
        a[poz] = val;
        return;
    }
    int mid = (left + right) / 2;
    if(mid >= poz)
        Update(Leftson(node), left, mid, poz, val);
    else
        Update(Rightson(node), mid + 1, right, poz, val);
    aint[node] = (aint[Leftson(node)] +  aint[Rightson(node)]) % mod;
}
void Query(int node, int left, int right, int a, int b)
{
    ///cout << left << " " << right << " " << node << "\n";
    if(a <= left && right <= b)
    {
        sum = (sum + aint[node]) % mod;
        return;
    }
    int mid = (left + right) / 2;
    if(a <= mid)
        Query(Leftson(node), left, mid, a, b);
    if(b > mid)
        Query(Rightson(node), mid + 1, right, a, b);

}

void Solve()
{
    int i;
    fin >> n >> k >> m;
    for(i = 1;i <= n;i++)
        fin >> a[i];
    for(i = 1;i <= m;i++)
    {
        int a, b;
        fin >> a >> b;
        Q[a].push_back({b, i});
    }
    for(i = n;i >= 1;i--)
    {
        if(last[a[i]])
            Update(1, 1, n, last[a[i]], 0);
        last[a[i]] = i;
        Update(1, 1, n, i, a[i]);
        for(auto q : Q[i])
        {
            sum = 0;
            Query(1, 1, n, i, q.first);
            sol[q.second] = sum;
        }
    }
    for(i = 1;i <= m;i++)
        fout << sol[i] << "\n";
}
int main()
{
    cout << sizeof(Q) /1024;
    Solve();
    return 0;
}