#include <cstdio>
#include <algorithm>

using namespace std;

struct quest { int st, dr, i; };

bool operator<(const quest &a, const quest &b) {
	return (a.st < b.st) || (a.st == b.st && a.dr < b.dr);
}

const int NMAX = 1 << 17;
const int MOD = 666013;

int N, K, M;
int A[NMAX], T[NMAX], V[NMAX];
quest Q[NMAX];
int AIB[NMAX];
int R[NMAX];

void update(int poz, int val) {
	for (; poz <= N; poz += poz & ~(poz - 1)) {
		AIB[poz] += val;
		if (AIB[poz] >= MOD) AIB[poz] -= MOD;
		if (AIB[poz] < 0) AIB[poz] += MOD;
	}
}

int query(int poz) {
	int rez = 0;

	for (; poz; poz -= poz & ~(poz - 1)) {
		rez += AIB[poz];
		if (rez >= MOD) rez -= MOD;
	}

	return rez;
}

void read(void) {
	FILE *fin = fopen("distincte.in", "rt");
	int i;

	fscanf(fin, " %d %d %d", &N, &K, &M);

	for (i = 1; i <= N; ++i) {
		fscanf(fin, " %d", A + i);
		
		if (V[A[i]] == 0)
			update(i, A[i]);
		else
			T[V[A[i]]] = i;

		V[A[i]] = i;
	}

	for (i = 0; i < M; ++i) {
		Q[i].i = i;
		fscanf(fin, " %d %d", &Q[i].st, &Q[i].dr);
	}

	fclose(fin);
}

void solve(void) {
	int i, j = 1;
	int st, dr, k;

	for (i = 0; i < M; ++i) {
		st = Q[i].st; dr = Q[i].dr;
		k = Q[i].i;

		for (; j < st; ++j) {
			update(j, -A[j]);

			if (T[j]) update(T[j], A[T[j]]);
		}

		R[k] = query(dr);
	}
}

void write(void) {
	FILE *fout = fopen("distincte.out", "wt");
	int i;

	for (i = 0; i < M; ++i)
		fprintf(fout, "%d\n", R[i]);

	fclose(fout);
}

int main(void) {

	read();

	sort(Q, Q + M);

	solve();

	write();

	return 0;
}