#include <fstream>
#include <algorithm>
#define NMAX 100005
#define MOD 666013

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

int v[NMAX], aib[NMAX],lastap[NMAX],n,res[NMAX];
struct QUERY {
	int l,r,ord;
} query[NMAX];

inline int lsb(int x) {return (x&(x-1))^x;}

void update_aib(int pos, int val) {
	while(pos<=n) {
		aib[pos]=(aib[pos]+val)%MOD;
		pos+=lsb(pos);
	}
}

int query_aib(int pos) {
	int sum=0;

	while(pos>0) {
		sum=(sum+aib[pos])%MOD;
		pos-=lsb(pos);
	}

	return sum;
}

bool comp(QUERY a, QUERY b) {
	return a.r<b.r;
}

int main() {
	int i,m,k,j;

	fin>>n>>k>>m;

	for(i=1;i<=n;++i) fin>>v[i];
	for(i=0;i<m;++i) {
		fin>>query[i].l>>query[i].r;
		query[i].ord=i;
	}

	sort(query,query+m,comp);

	j=1;
	for(i=0;i<m;++i) {
		for(;j<=query[i].r;++j) {
			if(lastap[v[j]]) update_aib(lastap[v[j]], -v[j]);
			update_aib(j, v[j]);
			lastap[v[j]]=j;
		}
		res[query[i].ord]=query_aib(query[i].r)-query_aib(query[i].l-1);
		if(res[query[i].ord]<0) res[query[i].ord]+=MOD;
	}

	for(i=0;i<m;++i) fout<<res[i]<<'\n';

	return 0;
}