#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
#define fin  "distincte.in"
#define fout "distincte.out"
#define Nmax 100100
#define Mod  666013

using namespace std;

struct nod { int k,st,dr; };

struct byst : public binary_function <nod, nod, bool> {
	bool operator()(nod T1, nod T2) { return T1.st < T2.st; }
};

struct byk : public binary_function <nod, nod, bool> {
	bool operator()(nod T1, nod T2) { return T1.k < T2.k; }
};


int N,K,M,sum[Nmax],f[Nmax];
nod v[Nmax];

vector <nod> m;		//retin intrebarile , in k pozitia ei initiala
			//in dr voi retine la sf raspunsul

void ins(int x,int val) {
	for ( ; x <= N ; x += x & ~ (x-1) )
		sum[x]=( sum[x] + val + Mod ) % Mod;
}

int query(int x) {
int ret=0;
	for ( ; x > 0 ; x -= x & ~ (x-1) )
		ret = ( ret + sum[x] ) % Mod;
	return ret;
}

int main() {
int i,j,ans;
nod aux;
	freopen(fin,"r",stdin); freopen(fout,"w",stdout);

	scanf("%d%d%d",&N,&K,&M);

	for (i=1;i<=N;++i) {
		scanf("%d",&v[i].k);
		v[i].st=f[v[i].k];
		v[i].dr=N+1;
		v[v[i].st].dr=i;
		f[v[i].k]=i;
		if (v[i].st==0)
			ins(i,v[i].k);
	}

	for (i=1;i<=M;++i) {
		scanf("%d%d",&aux.st,&aux.dr);
		aux.k=i;
		m.push_back(aux);
	}

	sort(m.begin(),m.end(),byst());	//sortez dupa capat stanga

	for (j=0,i=1;i<=N;++i) {

		for (;m[j].st==i;++j) {
			ans=( query(m[j].dr)-query(i-1)+Mod ) % Mod;	
			m[j].dr=ans;	
		}

		ins(i,-v[i].k); ins(v[i].dr,v[i].k);
	}
	
	sort(m.begin(),m.end(),byk());	//sirtez dupa indexul intrebarii
	
	for (i=0;i<(int)m.size();++i)
		printf("%d\n",m[i].dr);

	return 0;
}