#include <iostream>
#include <fstream>

using namespace std;

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

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

int dup[SZ];
int where_dup[SZ];
int sum[SZ + 1];
int sum_dup[SZ + 1];
int dup_first[SZ];
int dup_last[SZ];
int sum_first[SZ + 1];
int sum_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 = 0; i < N; i++) {
		f >> u;
		sum[i + 1] = mod(sum[i] + u);
		if (where_dup[u] == 0) {
			where_dup[u] = N + i;
		}
		else {
			dup[i] = u;
			if (where_dup[u] >= N) {
				dup[where_dup[u] - N]  = u;
				dup_first[where_dup[u] - N]  = u;
			}
			else {
				dup_last[where_dup[u]] = dup_last[where_dup[u]] - u;
			}
			dup_last[i] = u;
			where_dup[u] = i;
		}
	}
	for (i = 0; i < N; i++) {
		sum_dup[i + 1] = mod(sum_dup[i] + dup[i]);
		sum_first[i + 1] = mod(sum_first[i] + dup_first[i]);
		sum_last[i + 1] = mod(sum_last[i] + dup_last[i]);
	}
	ofstream g("distincte.out");
	for (i = 0; i < M; i++) {
		f >> qi >> qj;
		qi--;
		u = sum[qj] - sum[qi];
		if (qi < qj - 1) {
			u = u - sum_dup[qj] + sum_dup[qi];
			u = u + sum_first[qj] - sum_last[qi];
		}
		g << mod(u) << endl;
	}
	f.close();
	g.close();
	return 0;
}