#include <stdio.h>
int main()
{
	int n,k,m,i,a,b,j,d=0,c;
	int e[100005];
	bool g[100005];
	for(i=0;i<=100004;i++)
	{
		e[i]=0;
		g[i]=false;
	}
	FILE *f1,*f2;
	f1=fopen("distincte.in","r");
	f2=fopen("distincte.out","w");
	fscanf(f1,"%d %d %d",&n,&k,&m);
	for(i=1;i<=n;i++)
	{
		fscanf(f1,"%d",&a);
		e[i]=a;
	}
	for(i=1;i<=m;i++)
	{
		fscanf(f1,"%d %d",&a,&b);
		for(j=a;j<=b;j++)
		{		
			c=e[j];
			if(g[c]==false)d=d+c;
			g[c]=true;
		}
		d=d%666013;
		fprintf(f2,"%d\n",d);
		d=0;
		for(j=1;j<=100004;j++)
		{
			g[j]=false;
		}
	}
	fclose(f1);
	fclose(f2);
	return 0;
}