// http://infoarena.ro/problema/distincte

#include <cstdio>

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

const int TREEMAX = 1 << 18;
const int NMAX = 100002;
const int MOD = 666013;

int Tree[TREEMAX], A[NMAX], Prev[NMAX], Last[NMAX];
bool Found[NMAX];
int n, m, k;
vector<pair< pair<int, int>, int > > Queries;
vector<pair<int, int> > Ans;

inline int left(int i) {
	return 2 * i;
}
inline int right(int i) {
	return 2 * i + 1;
}

void treeBuild(int i, int l, int r) {
	if (l == r) {
		Tree[i] = A[l - 1];
		return;
	}
	
	int m = (r - l) / 2 + l;
	treeBuild(left(i), l, m);
	treeBuild(right(i), m + 1, r);
	
	Tree[i] = (Tree[left(i)] + Tree[right(i)]) % MOD;
}

void treeUpdate(int pos, int key, int i, int l, int r) {
	if (l == r && l == pos) {
		Tree[i] = key;
		return;
	}
	
	int m = (r - l) / 2 + l;
	if (pos <= m)
		treeUpdate(pos, key, left(i), l, m);
	else
		treeUpdate(pos, key, right(i), m + 1, r);
	
	Tree[i] = (Tree[left(i)] + Tree[right(i)]) % MOD;
}

int treeQuery(int wl, int wr, int i, int l, int r) {
	if (wl <= l && r <= wr)
		return Tree[i];
	
	int m = (r - l) / 2 + l, lv, rv;
	lv = rv = 0;
	if (wl <= m)
		lv = treeQuery(wl, wr, left(i), l, m);
	if (m < wr)
		rv = treeQuery(wl, wr, right(i), m + 1, r);
	
	return (lv + rv) % MOD;
}

int main() {
	
	freopen("distincte.in", "r", stdin);
	freopen("distincte.out", "w", stdout);
	
	scanf("%d %d %d", &n, &k, &m);
	int i;
	for (i = 1; i <= k; ++ i)
		Last[i] = -1;
	for (i = 0; i < n; ++ i) {
		scanf("%d", &A[i]);
		Prev[i] = Last[A[i]];
		Last[A[i]] = i;
		
		//printf("%d ", Prev[i]);
	}
	//printf("\n");
	
	treeBuild(1, 1, n);
	
	int x, y;
	for (i = 0; i < m; ++ i) {
		scanf("%d %d", &x, &y);
		Queries.push_back(make_pair(make_pair(y, x), i));
	}
	sort(Queries.begin(), Queries.end());
	
	int j, prev = -1, ans;
	for (i = 0; i < m; ++ i) {
		
		x = Queries[i].first.second, y = Queries[i].first.first;
		
		for (j = x - 1; j < y; ++ j)
			if (A[j] != 0 && Prev[j] != -1) {
				A[Prev[j]] = 0;
				treeUpdate(Prev[j] + 1, 0, 1, 1, n);
			}
			
		//printf("%d\n", treeQuery(x, y, 1, 1, n));
		ans = treeQuery(x, y, 1, 1, n);
		Ans.push_back(make_pair(Queries[i].second, ans));
		
		prev = y;
	}
	sort(Ans.begin(), Ans.end());
	
	for (i = 0; i < m; ++ i)
		printf("%d\n", Ans[i].second);
	
	return 0;
}