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

#define maxN 100100
#define maxS 400
#define cmod 666013

int n,k,m, vec[maxN],stor[maxN],nx[maxN],pr[maxN];
int r, seg[maxS][maxS];

void generate(){
	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,-1,(k+1)*sizeof*stor);for(int i=0;i<n;i++){int c=vec[i];if(stor[c]!=-1)pr[i]=stor[c];stor[c]=i;}
	r=sqrt((double)n);
	
	for(int i=0,j=0;i<n;i+=r,j++){
		int en=i+r,o,cs=j,ks=r,s=0;
		if(en>n)en=n;o=en;
		
		while(--o>=0){
			if(nx[o]>=en){s+=vec[o];while(s>=cmod)s-=cmod;}
			if(!--ks)seg[j][cs]=s,cs--,ks=r;
		}
	}
	
	
	
}

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,pr[i]=-1;
	generate();
	
	for(int i=0;i<m;i++){
		int a,b,s=0; fscanf(fi,"%d %d",&a,&b);a--;b--;
		int sb,se;
		sb=a/r;if(a%r)sb++; se=b/r-1;
		
		
		if(se<sb){
			for(int j=b;j>=a;j--)if(nx[j]>b){s+=vec[j];while(s>=cmod)s-=cmod;}
		}else{
		
			s=seg[se][sb];
			int bar=sb*r;
			for(int j=a,t=bar;j<t;j++){
				if(nx[j]>b){s+=vec[j];while(s>=cmod)s-=cmod;}
			}
			for(int j=b,t=se*r+r;j>=t;j--){
				if(pr[j]<bar){s+=vec[j];while(s>=cmod)s-=cmod;}
			}
			
		}
		
		fprintf(fo,"%d\n",s);
	}
	
	fclose(fi);fclose(fo);return 0;
}