#include <stdio.h>

#define infile "distincte.in"
#define outfile "distincte.out"
#define NMAX 100002
#define MOD 666013

FILE *fin,*fout;
int n,k,m;
int v[NMAX];
bool used[NMAX];

int solve(int start, int end)
  {
   int i,suma=0;
   if(end-start+1 < k)
     for(i=start;i<=end;i++)
        used[v[i]]=false;
   else
     for(i=0;i<k;i++)
        used[i]=false;
   for(i=start;i<=end;i++)
      if(!used[v[i]])
        {
         used[v[i]]=true;
         suma+=v[i];
         if(suma>=MOD)
           suma-=MOD;
        }
   return suma;
  }


int main()
{
char sir[20];
int i,j,number,start,end;
fin=fopen(infile,"r");
fout=fopen(outfile,"w");
fscanf(fin,"%d %d %d\n",&n,&k,&m);
for(i=0;i<n;i++)
   {
    fgets(sir,20,fin);
    number=0;
    j=0;
    while(sir[j]>='0' && sir[j]<='9')
         {
          number=number*10+(sir[j]-'0');
          j++;
         }
    v[i]=number;
   }
for(i=0;i<m;i++)
   {
    fgets(sir,20,fin);
    j=0;
    start=0;
    while(sir[j]>='0' && sir[j]<='9')
         {
          start=start*10+(sir[j]-'0');
          j++;
         }
    j++;
    end=0;
    while(sir[j]>='0' && sir[j]<='9')
         {
          end=end*10+(sir[j]-'0');
          j++;
         }
    start--;
    end--;
    fprintf(fout,"%d\n",solve(start,end));
   }
fclose(fin);
fclose(fout);
return 0;
}