#include <fstream>

using namespace std;

const int SZ = 100000;
const int MOD = 666013;

int orig[SZ + 1];
bool is_dup[SZ + 1];
int where_first[SZ + 1];
int where_last[SZ + 1];
int first[SZ + 1];
int last[SZ + 1];
long long sum_first[SZ + 1];
long long sum_last[SZ + 1];
int dup_first[SZ / 2];
int dup_last[SZ / 2];
int seq[SZ];
int left_seq[SZ + 1];
int right_seq[SZ + 1];
int query_dup[SZ + 1];

int main(int argc, char** argv) {
	int M, N, K;
	int qi, qj;
	int i, j, u, u_ant = 0, ndup = 0, nseq = 0;
	long long uu;
	ifstream f("distincte.in");
	f >> N >> K >> M;
	for (i = 1; i <= N; i++) {
		f >> u;
		orig[i] = u;
		last[i] = u;
		if (where_last[u] == 0) {
			where_first[u] = i;
			first[i] = u;
		}
		else {
			is_dup[u] = true;
			last[where_last[u]] = 0;
		}
		where_last[u] = i;
	}
	j = 0;
	for (i = 1; i <= N; i++) {
		left_seq[i] = nseq;
		u = orig[i];
		if (u != u_ant && is_dup[u]) {
			seq[nseq] = i;
			nseq++;
		}
		u_ant = u;
		right_seq[i] = nseq - 1;
		u = first[i];
		if (is_dup[u]) {
			dup_first[ndup] = u;
			ndup++;
		}
		u = last[N - i + 1];
		if (is_dup[u]) {
			dup_last[j] = u;
			j++;
		}
		sum_first[i] = sum_first[i - 1] + first[i];
		sum_last[i] = sum_last[i - 1] + last[i];
	}
	ofstream g("distincte.out");
	for (i = 1; i <= M; i++) {
		f >> qi >> qj;
		if (j <= N - i + 1) {
			uu = sum_first[qj] - sum_last[qi - 1];
			u = dup_first[0];
			for (j = 0; j < ndup && where_first[u] < qi && where_last[u] > qj; j++) {
				query_dup[u] = i;
				uu -= u;
				u = dup_first[j + 1];
			}
		}
		else {
			uu = sum_last[N] - sum_last[qi - 1];
			uu -= sum_first[N] - sum_first[qj];
			u = dup_last[0];
			for (j = 0; j < ndup && where_last[u] > qj && where_first[u] < qi; j++) {
				query_dup[u] = i;
				uu -= u;
				u = dup_last[j + 1];
			}
		}
		if (j > 0) {
			for (j = left_seq[qi]; j <= right_seq[qj]; j++) {
				u = orig[seq[j]];
				if (seq[j] >= qi && seq[j] <= qj && query_dup[u] == i) {
					query_dup[u] = 0;
					uu += u;
				}
			}
		}
		g << uu % MOD << '\n';
	}
	f.close();
	g.close();
	return 0;
}