#include <fstream>
#include <algorithm>

using namespace std;

const int Nmax = 100005;

int n, m, k, v[Nmax], sol[Nmax], lastPos[Nmax];
long long aint[4*Nmax];

struct qry{
    int st, dr, idx;
    bool operator < (const qry &a){
        return dr < a.dr;
    }
} q[Nmax];

void Update(int nod, int st, int dr, int poz, int val){
    if(st == dr){
        aint[nod] = val;
        return;
    }
    int mij = (st + dr) / 2;
    if(poz <= mij){
        Update(2*nod, st, mij, poz, val);
    }
    else{
        Update(2*nod+1, mij+1, dr, poz, val);
    }
    aint[nod] = aint[2*nod] + aint[2*nod+1];
}

int Query(int nod, int st, int dr, int a, int b){
    if(st == a && dr == b){
        return aint[nod];
    }
    int mij = (st + dr) / 2;
    if(b <= mij){
        return Query(2*nod, st, mij, a, b);
    }
    else{
        if(a > mij){
            return Query(2*nod+1, mij+1, dr, a, b);
        }
        else{
            return Query(2*nod, st, mij, a, mij) + Query(2*nod+1, mij+1, dr, mij+1, b);
        }
    }
}

int main(){
    ifstream fin("distincte.in");
    ofstream fout("distincte.out");
    fin >> n >> k >> m;
    for(int i = 1; i <= n; i++){
        fin >> v[i];
    }
    for(int i = 1; i <= m; i++){
        int st, dr;
        fin >> st >> dr;
        q[i] = {st, dr, i};
    }
    sort(q+1, q+m+1);

    int p = 1;
    for(int i = 1; i <= m; i++){
        while(p <= q[i].dr){
            Update(1, 1, n, p, v[p]);
            if(lastPos[v[p]] != 0){
                Update(1, 1, n, lastPos[v[p]], 0);
            }
            lastPos[v[p]] = p;
            p++;
        }
        sol[q[i].idx] = Query(1, 1, n, q[i].st, q[i].dr);
    }

    for(int i = 1; i <= m; i++){
        fout << sol[i] % 666013 << "\n";
    }

    return 0;
}