#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];
struct Data{
   int l;
   int r;
   int val;
};
Data V[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;
}
inline int query(int poz){
   int i;
   long long ans=0;
   for(i=poz;i>0;i-=zeros(i))
     ans+=aib[i];
   return ans%MOD;
}
bool cmp1(Query a,Query b){
    return a.r<b.r;
}
bool cmp2(Data a,Data 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<=n;i++){
      V[i].val=v[i];
      V[i].l=i;
      if(last[v[i]]<=i){
         j=i+1;
         while(j<=n&&v[j]!=v[i])
            j++;
         V[i].r=j;
         last[v[i]]=j;
      }
      else
         V[i].r=last[v[i]];
   }
   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,cmp1);
   std::sort(V+1,V+n+1,cmp2);
   poz=n;
   for(i=1;i<=m;i++){
      while(poz>0&&Q[i].r<V[poz].r){
         update(V[poz].l,V[poz].val);
         poz--;
      }
      rez[Q[i].poz]=query(Q[i].r)-query(Q[i].l-1);
      if(rez[Q[i].poz]<0)
        rez[Q[i].poz]+=MOD;
   }
   for(i=1;i<=m;i++)
     fprintf(fout,"%d\n" ,rez[i]);
   fclose(fi);
   fclose(fout);
   return 0;
}