#include <iostream>
#include <fstream>

using namespace std;

const int SZ = 100002;
const int MOD = 666013;

inline int mod(int a) {
	return (a + MOD) % MOD;
}

int where[SZ + 1];
int first[SZ + 1];
int last[SZ + 1];

int main(int argc, char** argv) {
	int M, N, K;
	int qi, qj;
	int i, u;
	ifstream f("distincte.in");
	f >> N >> K >> M;
	for (i = 1; i <= N; i++) {
		f >> u;
		last[i] = u;
		if (where[u] == 0) {
			first[i] = u;
		}
		else {
			last[where[u]] = 0;
		}
		where[u] = i;
	}
	for (i = 1; i <= N; i++) {
		first[i] = mod(first[i] + first[i - 1]);
		last[i] = mod(last[i] + last[i - 1]);
	}
	ofstream g("distincte.out");
	for (i = 0; i < M; i++) {
		f >> qi >> qj;
		u = first[qj] - last[qi - 1];
		g << mod(u) << endl;
	}
	f.close();
	g.close();
	return 0;
}