#include<stdio.h>
#define nmax 100005

int a[nmax];

int main()
{
FILE *fin=fopen("distincte.in","r"),
     *fout=fopen("distincte.out","w");
     
int n,i,j,k,m,x,y;
fscanf(fin,"%d %d %d",&n,&k,&m);
for(i=1;i<=n;i++)
   fscanf(fin,"%d",&a[i]);
   
int sol;
for(i=1;i<=m;i++)
   {
   fscanf(fin,"%d%d",&x,&y);
   sol=0;
   for(j=x;j<=y;j++)
      {
      k=x;
      while(k<j && a[k]!=a[j]) k++;
      if(k==j)
        {
        sol+=a[j];
        sol%=666013;        
        }
      }   
   fprintf(fout,"%d\n",sol);
   }
    
fclose(fin);
fclose(fout);
return 0;
}