#include <cstdio>
#include <algorithm>

using namespace std;

#define file_in "distincte.in"
#define file_out "distincte.out"

#define lsb(x) ((x)&(-(x)))
#define mod 666013
#define nmax 101000

int N,K,M,P[nmax],Aib[nmax],X[nmax],Y[nmax],V[nmax],ind[nmax],Sol[nmax];

void add(int poz, int val){
	
	int i;
	for (i=poz;i<=N;i+=lsb(i))
		 Aib[i]+=val;
}

int sol(int poz){
	
	int i,ans=0;
	for (i=poz;i>=1;i-=lsb(i))
		 ans+=Aib[i];
	return ans%mod;
}

int cmp(int a, int b){
	
	return (Y[a]<Y[b]);
}

int main(){
	
	int i,j;
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d %d", &N, &K, &M);
	for (i=1;i<=N;++i)
		 scanf("%d", &V[i]);
	for (i=1;i<=M;++i)
		scanf("%d %d", &X[i], &Y[i]),
		ind[i]=i;
	sort(ind+1,ind+M+1,cmp);
	j=1;
	for (i=1;i<=M;++i){
		while(j<=Y[ind[i]]){
			  add(j,V[j]);
			  if (P[V[j]])
				  add(P[V[j]],-V[j]);
			  P[V[j]]=j;
			  j++;
		}
		Sol[ind[i]]=sol(Y[ind[i]])-sol(X[ind[i]]-1);
		Sol[ind[i]]%=mod;
	}
	
	for (i=1;i<=M;++i)
		 printf("%d\n", Sol[i]);
	
	return 0;
}