#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5 + 5;
const int MOD = 666013;

#define pp pair<int, int>
#define st first
#define dr second

int n; int m; int k;

int v[NMAX];
int urm[NMAX];
int pre[NMAX];

int last[NMAX];
int aib[NMAX];//aib[i] = suma [i - 2 ^ bit(i) + 1 , i]
pp query[NMAX];
int sol[NMAX];
int ind[NMAX];
int cnt[NMAX];

inline int bit(int x) { return x & -x; }

struct cmp {

	bool operator()(const int& i, const int& j) {
		return query[i].dr <= query[j].dr;
	}

} cmpQ;

void ins(int pos, int value) {

	for( ; pos <= n ; pos += bit(pos)) {
		
		aib[pos] += value;

		if(aib[pos] >= MOD)
			aib[pos] -= MOD;
     	else if(aib[pos] < 0)
			aib[pos] += MOD;
	}
}

int que(int pos) {

	int sum = 0;

	for( ; pos > 0; pos -= bit(pos)) {
		sum += aib[pos];
		if(sum >= MOD)
			sum -= MOD;
	}

	return sum;
}

int main() {

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

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

	for(int i = 1; i <= n; ++i)
		scanf("%d", &v[i]), last[i] = n + 1;

	for(int i = n; i <= k ; ++i)
		last[i] = n + 1;

	for(int i = n ; i > 0 ; --i) {
		urm[i] = last[v[i]];
		last[v[i]] = i;
		pre[urm[i]] = i;
	}

	for(int i = 1; i <= m ; ++i)
		scanf("%d%d", &query[i].st, &query[i].dr), ind[i] = i;

	sort(ind + 1, ind + m + 1, cmpQ);

	for(int i = 1; i <= query[ind[1]].dr; ++i)
		if(urm[i] > query[ind[1]].dr)
			ins(i, v[i]);

	for(int i = 1; i <= m; ++i) {

		pp p = query[ind[i]];

		sol[ind[i]] =  que(p.dr) - que(p.st - 1);

		if(sol[ind[i]] < 0) sol[ind[i]] += MOD;

		for(int j = p.dr + 1 ; j <= query[ind[i + 1]].dr; ++j) {
			
			if(urm[j] > query[ind[i + 1]].dr)
				ins(j, v[j]);

			if(pre[j] != 0 && pre[j] <= p.dr) 
				ins(pre[j], -v[pre[j]]);	
		}
	}

	for(int i = 1; i <= m ; ++i)
		printf("%d\n", sol[i]);

	return 0;
}