#include <stdio.h>

#define maxN 100100
#define cmod 666013

int n,k,m, vec[maxN],stor[maxN],nx[maxN];

int main(){
	FILE*fi=fopen("distincte.in","r"),*fo=fopen("distincte.out","w");
	fscanf(fi,"%d %d %d",&n,&k,&m);for(int i=0;i<n;i++)fscanf(fi,"%d",vec+i),nx[i]=n; for(int i=0;i<=k;i++)stor[i]=-1;
	
	for(int i=n-1;i>=0;i--){
		int c=vec[i];
		if(stor[c]!=-1)nx[i]=stor[c];
		stor[c]=i;
	}
	
	for(int i=0;i<m;i++){
		int a,b,sum=0;fscanf(fi,"%d %d",&a,&b);a--;b--;
		
		for(;a<=b;a++){
			int c=vec[a];
			if(nx[a]>b){
				sum+=c;
				while(sum>=cmod)sum-=cmod;
			}
		}
		
		fprintf(fo,"%d\n",sum);
	}	
	
	fclose(fi);fclose(fo);return 0;
}