#include <fstream>
#include <algorithm>

#define MOD 666013

struct inter {
	int pos1, pos2, posi;
};

int nrn;

int vec[100005];
inter ask[100005];
int last[100005];
int aib[100005];
int ans[100005];

void update(int pos, int val){
	while (pos <= nrn) {
		aib[pos] += MOD + val;
		aib[pos] %= MOD;
		pos += (pos & -pos);
	}
}

int query(int pos) {
	int ans = 0;
	while (pos) {
		ans += MOD + aib[pos];
		ans %= MOD;
		pos &= (pos - 1);
	}
	return ans;
}

bool lastsort(inter nr1, inter nr2) {
	return nr1.pos2 < nr2.pos2;
}

int main() {
	std::ifstream fin("distincte.in");
	std::ofstream fout("distincte.out");
	int nrm, nrk;
	int sav;
	fin >> nrn >> nrk >> nrm;
	for (int index = 1; index <= nrn; index++) {
		fin >> vec[index];
	}
	for (int index = 0; index < nrm; index++) {
		fin >> ask[index].pos1 >> ask[index].pos2;
		ask[index].posi = index;
	}
	std::sort(ask, ask + nrm, lastsort);
	sav = 1;
	for (int index = 0; index < nrm; index++) {
		while (sav <= ask[index].pos2) {
			if (last[vec[sav]]) {
				update(last[vec[sav]], -vec[sav]);
			}
			last[vec[sav]] = sav;
			update(sav, vec[sav]);
			sav++;
		}
		ans[ask[index].posi] = query(ask[index].pos2) - query(ask[index].pos1 - 1);
	}
	for (int index = 0; index < nrm; index++) {
		fout << (ans[index] + MOD) % MOD << '\n';
	}
}