#include<fstream>
#define zeros(x) ( (x ^ (x - 1)) & x )
// solutie cu AIB
#define dim 100007
#define mod 666013

using namespace std;


ifstream f("distincte.in");
ofstream g("distincte.out");
int AIB[dim],next[dim],ant[dim],a,b,t[dim],cnt;
int i,j,n,m,k;

struct cub {
	int a,b,idx,sol;
}
S[dim];
int cmp1(cub a,cub b) {
	return a.a<b.a;
}
int cmp2(cub a,cub b){
	return a.idx<b.idx;
}
int add(int x,int val){
	
	for(int i=x;i<=n;i+=zeros(i)){
		AIB[i]+=val;
		if(AIB[i]<mod)
			AIB[i]+=mod;
		if(AIB[i]>=mod)
			AIB[i]-=mod;
	}
}
int comp (int x) {
	int sum=0;
	for(int i=x;i;i-=zeros(i)){
		sum+=AIB[i];
	}
	return sum%mod;
}
int main () {
	
	f>>n>>k>>m;
	
	for(i=1;i<=n;++i){
		f>>a;
		t[i]=a;
		next[ant[a]]=i;
		if(ant[a]==0){
			add(i,a);
		}
		ant[a]=i;
	}
	
	for(i=1;i<=m;++i  ){
		f>>a>>b;
		S[i].a=a;
		S[i].b=b;
		S[i].idx=i;
	}
	sort(S+1,S+1+m,cmp1);
	cnt=1;
	for(i=1;i<=n;++i) {
		
		while(S[cnt].a==i && cnt<=m){ 
			
			S[cnt].sol=comp(S[cnt].b);
			++cnt;
		}
		
		add(i,-t[i]);
		if(next[i]){
			add(next[i],t[i]);
		}
	}
	
	sort(S+1,S+1+m,cmp2);
	
	for(i=1;i<=m;++i){
		g<<S[i].sol<<"\n";
	}
	return 0;
}