#include <stdio.h>
#include <string.h>

#define maxN 100100
#define cmod 666013

int n,k,m, vec[maxN],stor[maxN],nx[maxN],sp[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;
	memset(stor,-1,(k+1)*sizeof*stor);
	for(int i=n-1;i>=0;i--){int c=vec[i];if(stor[c]!=-1)nx[i]=stor[c];stor[c]=i;}
	memset(stor,0,(k+1)*sizeof*stor);
	sp[0]=vec[0];stor[vec[0]]=1;
	for(int i=1;i<n;i++){
		int r=sp[i-1];
		if(!stor[vec[i]]){
			r+=vec[i]; while(r>=cmod)r-=cmod;
			stor[vec[i]]=1;
		}
		sp[i]=r;
	}
	
	
	for(int i=0;i<m;i++){
		int a,b,sum=0;fscanf(fi,"%d %d",&a,&b);a--;b--;
		
		if(b-a < a){
			for(;a<=b;a++){
				int c=vec[a];
				if(nx[a]>b){
					sum+=c;
					while(sum>=cmod)sum-=cmod;
				}
			}
		}else{
			sum=sp[b];
			for(int j=0;j<a;j++){
				int c=vec[j],g=nx[j];
				if(b<g){
					sum-=c; while(sum<0)sum+=cmod;
				}
			}
		}
		
		fprintf(fo,"%d\n",sum);
	}	
	
	fclose(fi);fclose(fo);return 0;
}