#include <stdio.h>

#define maxN 100100
#define cmod 666013

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