#include <stdio.h>
#define input "distincte.in"
#define output "distincte.out"
#define rest 666013
#define nmax 100001
long n,k,m,i,j,a,b,sum,fol[nmax],v[nmax];
int main()
{
	FILE *fin,*fout;
	fin=fopen(input,"r");
	fout=fopen(output,"w");
	fscanf(fin,"%ld %ld %ld",&n,&k,&m);
	for (i=1;i<=n;i++)
		fscanf(fin,"%ld",&v[i]);
	for (i=1;i<=m;i++)
		{
		 fscanf(fin,"%ld %ld",&a,&b);
		 sum=0;
		 for (j=a;j<=b;j++)
			{
			 if (fol[v[j]]!=i) 
				{
				 fol[v[j]]=i;
				 sum+=v[j];
				}
			 if (sum>=rest) sum-=rest;
			}
		 fprintf(fout,"%ld\n",sum);
		}
	fclose(fin);
	fclose(fout);
	return 0;
}