#include <cstdio>
#include <algorithm>
using namespace std;

const int NMAX = 100001;
const int MOD = 666013;

class query {
	public:
	int l, r, i;
	query() {
	}
}q[NMAX];

inline bool cmpQ(query a, query b) {
	return a.r > b.r ? 1 : 0;
}

int v[NMAX], next[NMAX], lastPos[NMAX], order[NMAX], N, K, M;
int ans[NMAX]; //Raspunsul la query-uri

inline bool cmp(int a, int b) {
	return next[a] > next[b] ? 1 : 0;
}

int aib[4 * NMAX];
void add(int a, int val, int nod, int l, int r) { //Adauga in AIB
	if (l > r) return;
	if (a < l || a > r) return;
	aib[nod] += val;
	if (aib[nod] >= MOD) {
		aib[nod] -= MOD;
	}
	if (l != r) {
		add(a, val, nod<<1, l, (l + r)>>1);
		add(a, val, (nod<<1) + 1, ((l + r)>>1) + 1, r);
	}
}

int ask(int st, int dr, int nod, int l, int r) {
	if (dr < l || st > r) return 0;
	if (st <= l && dr >= r) return aib[nod];
	return (ask(st, dr, nod<<1, l, (l + r)>>1) + ask(st, dr, (nod<<1) + 1, ((l + r)>>1) + 1, r)) % MOD;
}

	
int main() {
	FILE *fin = fopen("distincte.in", "r");
	FILE *fout = fopen("distincte.out", "w");
	fscanf (fin, "%d %d %d", &N, &K, &M);
	int i;
	for (i = 1; i <= N; ++i) {
		fscanf (fin, "%d", &v[i]);
	}
	for (i = 1; i <= M; ++i) {
		fscanf (fin, "%d %d", &q[i].l, &q[i].r);
		q[i].i = i;
	}
	sort(q + 1, q + M + 1, cmpQ);
	for (i = 1; i <= K; ++i) {
		lastPos[i] = N + 1;
	}
	for (i = N; i; i--) {
		next[i] = lastPos[v[i]];
// 		printf ("Next %d = %d\n", i, next[i]);
		lastPos[v[i]] = i;
		order[i] = i;
	}
	sort(order + 1, order + N + 1, cmp);
// 	printf ("Am sortat dupa NEXT\n");
	int ii = 1;
	for (i = 1; i <= M; ++i) {
// 		printf ("I = %d\n", i);
		for (;ii <= N && next[order[ii]] > q[i].r; ii++) { //Adaug nodurile care sunt distincte
			add(order[ii], v[order[ii]], 1, 1, N);
		}
		//
		ans[q[i].i] = ask(q[i].l, q[i].r, 1, 1, N);
	}
// 	printf ("Aici\n");
	for (i = 1; i <= M; ++i) {
		fprintf (fout, "%d\n", ans[i]);
	}
	fclose(fout);
	return 0;
}