#include <cstdio>
#include <algorithm>
#define f first
#define s second
using namespace std;
const int N = 100005;
const int MOD =  666013;
int n, m, a[N], l[N], k;
struct tip{int f, s, o;} q[N];
long long aib[N], v[N];
int cmp(tip a, tip b) {
	return a.s < b.s;
}

inline void update(int x, int val) {
	for(;x <= n; x += (x ^ (x - 1)) & x){
		aib[x] +=(long long) val;
		aib[x] %= MOD;
	}
}

inline long long query(int x) {
	long long s = 0;
	for(;x; x -= (x ^ (x - 1)) & x) {
		s += aib[x];
		s %= MOD;
	}
	return s;
}

int main() {
	freopen("distincte.in", "r", stdin);
	freopen("distincte.out", "w", stdout);
	int i;
	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", &q[i].f, &q[i].s), q[i].o = i;

	for(i = 1; i <= n; ++i) {
		l[i] = v[a[i]];
		v[a[i]] = i;
	}

	sort(q + 1, q + m + 1, cmp);
	
	for(i = 1; i <= n; ++i) {
		if(l[i]) {
			update(l[i], - a[i]);
			update(i, a[i]);
		}
		if(i == q[i].s) 
			v[q[i].o] = (query(q[i].s) - query(q[i].f - 1) + MOD) % MOD;
	}

	for(i = 1; i <= m; ++i)
		printf("%lld\n", v[i]);

	return 0;
}