#include <bits/stdc++.h>
#define maxn 100005
std::ifstream fin ("distincte.in");
std::ofstream fout ("distincte.out");

long long aib[maxn];
void update (int n, int pos,int val){
    while (pos < n){
        aib[pos] += val;
        pos = (pos | (pos+1));
    }
}
long long queryAib (int pos){
    long long ans = 0;
    while (pos >= 0){
        ans += aib[pos];
        pos = (pos & (pos+1)) - 1;
    }
    return ans;
}

struct Queries{
    int left, right;
    int index;
    int ans;
}query[maxn];

struct Point{
    int x, y;
    int val;
}p[maxn];
int x[maxn];
int last[maxn];

bool sortQueries (Queries a, Queries b){
    return a.right > b.right;
}
bool sortPoints (Point a, Point b){
    return a.y > b.y;
}
bool sortIndex (Queries a, Queries b){
    return a.index < b.index;
}

int main()
{
    int n, k, Q, i;
    fin >> n >> k >> Q;
    for (i=0; i<n; i++)
        fin >> x[i];

    for (i=n-1; i>=0; i--){
        if (last[x[i]] == 0){
            p[i] = {i, n, x[i]};
            last[x[i]] = i;
        }
        else{
            p[i] = {i, last[x[i]], x[i]};
            last[x[i]] = i;
        }
    }

    //for (i=0; i<n; i++)
    //    fout << p[i].x << ' ' << p[i].y << '\n';

    for (i=0; i<Q; i++)
        fin >> query[i].left >> query[i].right,
        query[i].index = i,
        query[i].left --,
        query[i].right --;
    std::sort (query, query+Q, sortQueries);

    std::sort (p, p+n, sortPoints);
    int crt = 0;
    for (i=0; i<Q; i++){
        while (crt < n and p[crt].y > query[i].right){
            update (n, p[crt].x, p[crt].val);
            crt ++;
        }
        query[i].ans = queryAib (query[i].right) - queryAib (query[i].left-1);
    }

    std::sort (query, query+Q, sortIndex);

    for (i=0; i<Q; i++)
        fout << query[i].ans % 666013 << '\n';


    return 0;
}