#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

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

struct quest { int b, e, i; };

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

int N, K, M;
int A[NMAX];
quest Q[NMAX];
int end[NMAX], beg[NMAX];
int rez[NMAX];

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

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

	for (i = 0; i < N; ++i)
		fscanf(fin, " %d", A + i);

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

	fclose(fin);
}

void bulan(void) {
	int i, ne = 0, nb = 0;
	int se = 0, sb = 0;

	for (i = 0; i < M; ++i) {
		
		for (; ne <= Q[i].e; ++ne) {
			if (end[A[ne]] == 0) {
				se += A[ne];
				if (se >= MOD) se -= MOD;
			} else if (beg[A[ne]] == end[A[ne]]) {
				sb -= A[ne];
				if (sb < 0) sb += MOD;
			}

			++end[A[ne]];
		}

		if (nb > Q[i].b + 1) {
			nb = 0; sb = 0;
			memset(beg, 0x00, K * sizeof(int));
		}
	
		for (; nb <= Q[i].b; ++nb) {
			++beg[A[nb]];

			if (beg[A[nb]] == end[A[nb]]) sb += A[nb];
			if (sb >= MOD) sb -= MOD;
		}

		rez[Q[i].i] = se - sb;
		if (rez[Q[i].i] < 0) rez[Q[i].i] += MOD;
	}
}

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

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

	fclose(fout);
}

int main(void) {

	read();

	sort(Q, Q + M);

	bulan();

	write();

	return 0;
}