#include <bits/stdc++.h>
using namespace std;
ifstream fin ("distincte.in");
ofstream fout ("distincte.out");
#define int long long

const int MAXN=1e5+10;
const int MOD=666013;


struct query{
    int x,y,i;
}b[MAXN];
int n,q,a[MAXN],aib[MAXN],k,rez[MAXN];
vector <int> v[MAXN];
int pos[MAXN];

void update (int pos, int val){
    for (int i=pos;i<=n;i+=(i&(-i))){
        aib[i]+=val;
    }
}
int queryaib (int x){
    int rez1=0;
    for (int i=x;i>=1;i-=(i&(-i))){
        rez1+=aib[i];
    }
    return rez1;
}
int queryaib (int x, int y){
    return queryaib (y)-queryaib (x-1);
}

bool cmp (query a, query b){
    return a.x<b.x;
}

void del (int i){
    int x=a[i];
    if (pos[x]==v[x].size ())return;

    update (v[x][pos[x]],x);
    pos[x]++;
}

void solvequery (query a){
    rez[a.i]=queryaib (a.x,a.y);
}



signed main()
{

    fin >>n>>k>>q;
    for (int i=1;i<=n;++i){
        fin >>a[i];
        v[a[i]].push_back (i);
    }
    for (int i=1;i<=n;++i){
        if (v[i].size ()){
            update (v[i][0],i);
            pos[i]=1;
        }
    }

    for (int i=1;i<=q;++i){
        fin >>b[i].x>>b[i].y;
        b[i].i=i;
    }
    sort (b+1,b+q+1,cmp);

    int j=1;
    for (int i=1;i<=n;++i){
        ///i ul este capatul din stanga

        while (j<=q and b[j].x==i){

            solvequery (b[j]);
            j++;
        }
        del (i);

    }

    for (int i=1;i<=q;++i){
        fout <<rez[i]%MOD<<'\n';
    }
    return 0;
}