#include <bits/stdc++.h>

using namespace std;
const int modu=666013;
int n,k,m,nr,previ[100005],last[100005],aib[100005],v[100005],ans[100005],suma;vector < pair <int,int> > q[100005];
int lsb (int nr) {
	return (nr & (-nr));
}
void updatee (int nr, int poz) {
	while(poz<=n) {
		aib[poz]=(aib[poz]+nr)%modu;
		poz+=lsb(poz);
	}
}
int querrys (int dr) {
	suma=0;
	while(dr>0) {
		suma=(suma+aib[dr])%modu;
		dr-=lsb(dr);
	}
	return suma;
}
int main () {
	int nr1,nr2;
	freopen("distincte.in","r",stdin);
	freopen("distincte.out","w",stdout);
	scanf("%d%d%d", &n, &k, &m);
	for(int i=1;i<=n;++i) {
		scanf("%d", &nr);v[i]=nr;
		if(last[nr]!=0)
			previ[i]=last[nr];
		last[nr]=i;
	}
	for(int i=1;i<=m;++i) {
		scanf("%d%d", &nr1, &nr2);
		q[nr2].push_back(make_pair(nr1,i));
	}
	for(int i=1;i<=n;++i) {
		updatee(v[i],i);
		if(previ[i]!=0)
			updatee(-v[i],previ[i]);
		for(int ii=0;ii<(int)q[i].size();++ii) {
			ans[q[i][ii].second]=querrys(i)-querrys(q[i][ii].first-1);
			while(ans[q[i][ii].second]<0)
				ans[q[i][ii].second]+=modu;
		}
	}
	for(int i=1;i<=m;++i)
		printf("%d\n", ans[i]);
	return 0;
}