#include <stdio.h>
#define MOD 666013
#define MAXN 100000
#define MAXM 100000
#define MAXK 100000
int v[MAXN+1], aib[MAXN+1], a[MAXM+1], b[MAXM+1], ind[MAXM+1], prev[MAXK+1], sol[MAXM+1], n, m;
inline void update(int p, int x){
    if(p==0){
        return ;
    }
    while(p<=n){
        aib[p]+=x;
        if(aib[p]<0){
            aib[p]+=MOD;
        }
        if(aib[p]>=MOD){
            aib[p]-=MOD;
        }
        p+=p&(-p);
    }
}
inline int query(int p){
    int rez=0;
    while(p>0){
        rez+=aib[p];
        if(rez>=MOD){
            rez-=MOD;
        }
        p-=p&(-p);
    }
    return rez;
}
inline int tata(int p){
    return (p-1)/2;
}
inline int fiust(int p){
    return 2*p+1;
}
inline int fiudr(int p){
    return 2*p+2;
}
inline int cmp(int x, int y){
    if(b[x]==b[y]){
        return (a[x]<a[y]);
    }
    return (b[x]<b[y]);
}
inline void swap(int x, int y){
    int aux=a[x];
    a[x]=a[y];
    a[y]=aux;
    aux=b[x];
    b[x]=b[y];
    b[y]=aux;
    aux=ind[x];
    ind[x]=ind[y];
    ind[y]=aux;
    aux=v[x];
    v[x]=v[y];
    v[y]=aux;
}
inline void coborare(int p){
    int f=1, q;
    while((f==1)&&(fiust(p)<m)){
        q=fiust(p);
        if((fiudr(p)<m)&&(cmp(q, fiudr(p)))){
            q=fiudr(p);
        }
        if(cmp(p, q)){
            swap(p, q);
            p=q;
        }else{
            f=0;
        }
    }
}
inline void heapify(){
    int i;
    for(i=tata(m-1); i>=0; i--){
        coborare(i);
    }
}
inline void heapSort(){
    int cm=m;
    while(m>1){
        m--;
        swap(0, m);
        coborare(0);
    }
    m=cm;
}
int main(){
    int k, i, poz;
    FILE *fin, *fout;
    fin=fopen("distincte.in", "r");
    fout=fopen("distincte.out", "w");
    fscanf(fin, "%d%d%d", &n, &k, &m);
    for(i=1; i<=n; i++){
        fscanf(fin, "%d", &v[i]);
    }
    for(i=0; i<m; i++){
        fscanf(fin, "%d%d", &a[i], &b[i]);
        ind[i]=i;
    }
    heapify();
    heapSort();
    poz=0;
    for(i=0; i<m; i++){
        while(poz<b[i]){
            poz++;
            update(prev[v[poz]], -v[poz]);
            update(poz, v[poz]);
            prev[v[poz]]=poz;
        }
        sol[ind[i]]=query(b[i])-query(a[i]-1);
        if(sol[ind[i]]<0){
            sol[ind[i]]+=MOD;
        }
    }
    for(i=0; i<m; i++){
        fprintf(fout, "%d\n", sol[i]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}