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

const int MAX_N = 100010;
const int MOD = 666013;

struct query{
	int x, y;
	int loc;
	int rez;
};

int n, k, m;
int a[MAX_N], last[MAX_N];
int aib[MAX_N];
query d[MAX_N];

inline int cmp(query a, query b) {
	return a.y < b.y;
}

inline int cmp2(query a, query b) {
	return a.loc < b.loc;
}

void update(int x, int y) {
	while (x <= n) {
		aib[x] += y;
		aib[x] %= MOD;
		x += x ^ (x - 1) & x;
	}
}

int query(int x) {
	int val = 0;
	while (x) {
		val += aib[x];
		val %= MOD;
		x &= x - 1;
	}

	return val;
}

int main()
{
	int i;
	freopen("distincte.in", "r", stdin);
	freopen("distincte.out", "w", stdout);

	scanf("%d %d %d", &n, &k, &m);
	for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for (i = 1; i <= m; ++i) {
		scanf("%d %d", &d[i].x, &d[i].y);
		d[i].loc = i;
	}

	sort(d + 1, d + m + 1, cmp);

	int j = 1;

	for (i = 1; i <= n; ++i) {
		update(i, a[i]);

		if (last[a[i]] > 0)
			update(last[a[i]], -a[i]);

		last[a[i]] = i;

		while (i == d[j].y)
			d[j++].rez = (query(d[j].y) + MOD) - query(d[j].x - 1);
	}

	sort(d + 1, d + m + 1, cmp2);

	for (i = 1; i <= m; ++i) 
		printf("%d\n", d[i].rez % MOD);
}