#include<stdio.h>
int x[100000],n,m,k, viz[100000];
FILE *f=fopen("distincte.in","r");
FILE *g=fopen("distincte.out","w");
void init()
{int i;
 for(i=1;i<=k;i++)
  viz[i]=0;}
void citire()
{int i;
 fscanf(f,"%d %d %d",&n,&k,&m);
 for(i=1;i<=n;i++)
  fscanf(f,"%d",&x[i]);
 }
int det(int i,int j)
{int s=0,l;init();
 for(l=i;l<=j;l++)
  if(!viz[x[l]]) {s+=x[l];viz[x[l]]=1;}
 return s;}
int main()
{int i,a,b,c;
 citire();
 for(i=1;i<=m;i++)
  {fscanf(f,"%d %d",&a,&b);
   c=det(a,b)%666013;
   fprintf(g,"%d\n",c);}
 fcloseall();                        
 return 0;}