#include <bits/stdc++.h>

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

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];

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;

		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() {

	ios::sync_with_stdio(false);

	fin >> n >> k >> m;

	for(int i = 1; i <= n; ++i)
		fin >> v[i];

	for(int i = 1; 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)
		fin >> 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)
		fout << sol[i] << '\n';

	return 0;
}