//trimisesem codu vechi, va rog sa ma iertati



#include <bits/stdc++.h>
using namespace std;
struct query {
	int l,r,idx;
};
vector<long long> aib;
vector<int> v;
vector<int> ante;
vector<long long> ans;
vector<query> queries;
int n,k,q,i,j,l,r,idx;
void update(int i, int val){
	for (;i<=n;i+=(i & (-i)))
		aib[i]+=val;
}
long long take(int i){
	long long sum = 0;
	for (;i>0;i-=(i&(-i)))
		sum+=aib[i];
	return sum;
}
bool cmp(query a, query b) {
	return a.r<b.r;
}
int main() {
    ifstream fin("distincte.in");
    ofstream fout("distincte.out");
	fin >> n >> k >> q;
	aib.resize(n+2);
	v.resize(n+2);
	ante.resize(k+2);
	ans.resize(q);
	queries.resize(q);
	for(i=1;i<=n;i++)
		fin >> v[i];
	for(i=0;i<q;i++){
		fin >> queries[i].l >> queries[i].r;
		queries[i].idx = i;
	}
	sort(queries.begin(), queries.end(), cmp);
	j=0;
	for(i = 1; i <= n; i++){
		if (ante[v[i]]!=0)
			update(ante[v[i]],-v[i]);
		update(i,v[i]);
		ante[v[i]]=i;
		while(j<q&&queries[j].r==i){
			l=queries[j].l;
            r=queries[j].r;
			idx=queries[j].idx;
			ans[idx]=(take(r)-take(l-1))%666013;
			j++;
		}
	}
	for(i=0;i<q;i++)
		fout << ans[i] << '\n';
	return 0;
}