#include<stdio.h>
int a[10000];
long n,m,k;
FILE *f=fopen("distincte.in","r");
FILE *g=fopen("distincte.out","w");




void rez(long x,long y)
{ 
 int d[10000];
 long nrk,i,j,suma;

 suma=0;
 if(x==1&&y==n)
       {for(i=1;i<=k;i++)
	suma+=i;
       fprintf(g,"%ld\n",suma%666013);
	}
 else
	{ nrk=0;
	for(i=x;i<=y;i++)
	   {int sw=1;
	  for(j=1;j<=nrk;j++)
	  if(a[i]==d[j])
	       {sw=0;break;}
	    if(sw)
	     d[++nrk]=a[i];
	  if(nrk==k)
	 break;}

for(i=1;i<=nrk;i++)
 suma+=d[i];
fprintf(g,"%ld\n",suma%666013);
}

}

void cit()
{  long i;
  fscanf(f,"%ld%ld%ld",&n,&k,&m);
  for(i=1;i<=n;i++)
 fscanf(f,"%d",&a[i]);
 
long x,y;  
for(i=1;i<=m;i++)
   {fscanf(f,"%ld%ld",&x,&y);
   rez(x,y);
  }

}

int main()
{
 cit();
 fcloseall();
  return 0;
}