#include <cstdio>
#define INF "distincte.in"
#define OUF "distincte.out"
#define SEGT 200002
#define NMAX 100002
#define CLB 666013
using namespace std;

unsigned *segt[SEGT],*rez,mask[32],n,m,hdim,op,a,b;
unsigned segtt[SEGT]={0};
void insert(unsigned nod, unsigned li,unsigned ls)
{
   if(a<=li&&ls<=b) 
   {
	   segt[nod][op/32]|=mask[op%32];
	   segtt[nod]=op;
   }
   else
   {
       unsigned mij;
       mij=(li+ls)/2;
       if(a<=mij) insert(2*nod,li,mij);
       if(b>mij) insert(2*nod+1,mij+1,ls);
       if((segt[nod][op/32]&mask[op%32])==0)
       {
	       segt[nod][op/32]|=mask[op%32];
	       segtt[nod]+=op;
       }
   }
}
void query(unsigned nod,unsigned li,unsigned ls)
{
	if(a<=li&&ls<=b)
	{
		register unsigned i,db,j;
		op+=segtt[nod];
		for(i=0;i<hdim;i++)
		{
		        db=rez[i]&segt[nod][i];
			rez[i]|=segt[nod][i];
			if(db) for(j=0;j<32;j++)if(db&mask[j]) op-=(i*32+j);
		}
	}
	else
	{
		int mij;
		mij=(li+ls)/2;
		if(a<=mij) query(2*nod,li,mij);
		if(b>mij)  query(2*nod+1,mij+1,ls);
	}
}
int main()
{
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	register unsigned i,j,aux;
	unsigned *p;
	fscanf(in,"%u %u %u",&n,&op,&m);
	hdim=op/32+1;
	for(i=0;i<32;i++) mask[i]=(1<<i);
	aux=n;j=0;
	while(aux){ aux/=2;j++; }
	aux=(1<<(j+1));
	
	for(i=1;i<=aux;i++)
	{
		segt[i]=new unsigned[hdim];
		p=segt[i];
		for(j=0;j<hdim;j++) p[j]=0;
	}
	rez=new unsigned[hdim];
 
	for(i=1;i<=n;i++)
	{
		fscanf(in,"%u",&op);
		a=b=i;
		insert(1,1,n);
	}

	for(i=1;i<=m;i++)
	{
		for(j=0;j<hdim;j++) rez[j]=0;
		fscanf(in,"%u %u",&a,&b);
		op=0;
		query(1,1,n);
		fprintf(out,"%u\n",op%CLB);
	}

	fclose(in);fclose(out);
	return 0;
}