#include <cstdio>
#include <algorithm>
#include <cctype>
#define MAXBUF 1<<17
FILE*fi,*fout;
char buf[MAXBUF];
int pos=MAXBUF;
inline char nextch(){
    if(pos==MAXBUF){
        fread(buf,1,MAXBUF,fi);
        pos=0;
    }
    return buf[pos++];
}
inline int getnr(){
   char a=nextch();
   while(isdigit(a)==0)
      a=nextch();
   int nr=0;
   while(isdigit(a)==1){
      nr=nr*10+a-'0';
      a=nextch();
   }
   return nr;
}
#define MAXN 100000
#define MOD 666013
#define zeros(x) (x&(-x))
struct Query{
   int l;
   int r;
   int poz;
};
Query Q[MAXN+1];
int aib[MAXN+1];
int rez[MAXN+1];
int last[MAXN+1];
int v[MAXN+1];
int n;
inline void update(int poz,int val){
    int i;
    for(i=poz;i<=n;i+=zeros(i)){
      aib[i]+=val;
      if(aib[i]>=MOD)
         aib[i]-=MOD;
      if(aib[i]<0)
         aib[i]+=MOD;
    }
}
inline int query(int poz){
   int i;
   int ans=0;
   for(i=poz;i>0;i-=zeros(i)){
     ans+=aib[i];
     if(ans>=MOD)
       ans-=MOD;
   }
   return ans;
}
bool cmp(Query a,Query b){
    return a.r<b.r;
}
int main(){
   int i,k,m,poz,j;
   fi=fopen("distincte.in" ,"r");
   fout=fopen("distincte.out" ,"w");
   n=getnr();
   k=getnr();
   m=getnr();
   for(i=1;i<=n;i++)
     v[i]=getnr();
   for(i=1;i<=m;i++){
      Q[i].l=getnr();
      Q[i].r=getnr();
      Q[i].poz=i;
   }
   std::sort(Q+1,Q+m+1,cmp);
   poz=1;
   for(i=1;i<=n;i++){
      update(i,v[i]);
      if(last[v[i]]>0)
         update(last[v[i]],-v[i]);
      last[v[i]]=i;
      while(poz<=m&&Q[poz].r==i){
         rez[Q[poz].poz]=query(Q[poz].r)-query(Q[poz].l-1);
         if(rez[Q[poz].poz]<0)
           rez[Q[poz].poz]+=MOD;
         poz++;
      }
   }
   for(i=1;i<=m;i++)
     fprintf(fout,"%d\n" ,rez[i]);
   fclose(fi);
   fclose(fout);
   return 0;
}