using namespace std;
#include<fstream>
#include<stdio.h>
#define nmax 100005

int a[nmax];
int u[nmax];

int main()
{
FILE *fin=fopen("distincte.in","r"),
     *fout=fopen("distincte.out","w");
     
memset(u,0,sizeof u);
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++)
     if(u[a[j]]==0)
      {
      u[a[j]]=1;
      sol+=a[j];
      sol%=666013;                    
      }
      
   for(j=x;j<=y;j++)
      u[a[j]]=0;
      
   fprintf(fout,"%d\n",sol);
   }
    
fclose(fin);
fclose(fout);
return 0;
}