#include<stdio.h>

void init(int viz[],int k){
	int i;
	for(i=0;i<k;i++) viz[i]=0;
}

int main(){

int n,k,m,v[100000],i,j,x,y,viz[100000],sum;
freopen("distincte.in","r",stdin);
freopen("distincte.out","w",stdout);
scanf("%d %d %d ",&n,&k,&m);
for(i=0;i<n;i++)
	scanf("%d\n",&v[i]);
for(i=0;i<m;i++){
	scanf("%d %d ",&x,&y);
	sum=0;
	init(viz,k);
	for(j=x-1;j<y;j++)
		if(!viz[v[j]-1]){
			sum+=v[j];
			viz[v[j]-1]=1;
			if(sum>666013)
			sum-=666013; }
	printf("%d\n",sum);
}
return 0;
}