#include <bits/stdc++.h>
using namespace std;

#define MOD 666013
#define NMAX 100002

int n, m, k;
int aib[NMAX], a[NMAX], viz[NMAX];

int zero(int x) { return (x ^ (x - 1)) & x; }

void update(int pos, int val) {
	for (int i = pos; i <= n; i += zero(i))
		aib[i] = (aib[i] + val) % MOD;
}

int query(int pos) {
	int result = 0;
	for(int i = pos; i > 0; i -= zero(i))
		result = (result + aib[i]) % MOD;
	return result;
}

int rangeQuery(int x, int y) {
	return query(y) - query(x - 1) + 1;
}

void read() {
	scanf("%d %d %d ", &n, &k, &m);

	for (int i = 1; i <= n; i++) {
		scanf("%d ", &a[i]);
	}

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

		if (viz[a[i]]) {
			update(viz[a[i]], -a[i]);
		}

		viz[a[i]] = i;
	}
}

void solve() {
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d %d ", &x, &y);
		printf("%d\n", rangeQuery(x, y) % MOD);
	}
}


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

	read();
	solve();

	return 0;
}