#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *f,*g;
int aib[100001],best[100001],val[100001],n,m,k;
const int MOD=666013;
int next(int i){
    return (i<<1)-(i&(i-1));
}
int prev(int i){
    return i&(i-1);
}
void update(int a,int b){
    while (a<=n){
        aib[a]=(aib[a]+b)%MOD;;
        a=next(a);
    }
}
int query(int a){
    int sol=0;
    while (a>0){
        sol=(sol+aib[a])%MOD;;
        a=prev(a);
    }
    return sol;
}
int query(int a,int b){
    return (query(b)-query(a-1))%MOD;
}
struct pereche{
    int v1,v2,index,answer;
    bool operator < (const pereche b) const{
        return v2<b.v2;
    }
    
    
}dumm,intrb[100001];
bool cmp(pereche a, pereche b){
    return a.index<b.index;
}
void read(void){
    int i,a,b;
    f=fopen("distincte.in","r");
    g=fopen("distincte.out","w");
    fscanf(f,"%d%d%d",&n,&k,&m);
    for(i=1;i<=n;i++){
        fscanf(f,"%d",&val[i]);
        update(i,val[i]);
    }
    for(i=1;i<=m;i++){
        fscanf(f,"%d%d",&a,&b);
        dumm.v1=a;
        dumm.v2=b;
        dumm.index=i;
        intrb[i]=dumm;
    }
}

void answer(void){
    sort(intrb+1,intrb+m+1);
    int curr=1,i,j;
    best[val[1]]=1;
    for(i=1;i<=m;i++){
        if (curr==intrb[i].v2){
            intrb[i].answer=query(intrb[i].v1,intrb[i].v2);
        }
        else {
            for(j=curr+1;j<=intrb[i].v2;j++){
                if (best[val[j]]) update(best[val[j]],-val[j]);
                best[val[j]]=j;

            }
            curr=intrb[i].v2;
            intrb[i].answer=query(intrb[i].v1,intrb[i].v2);
        }
        
    }
    sort(intrb+1,intrb+m+1,cmp);
}
int main(void){
    int i;
    read();
    answer();
    for(i=1;i<=m;i++){
        fprintf(g,"%d\n",intrb[i].answer);
    }
}