#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

struct query_int {
	int s, f, orig_poz;
	long long rez;
};

const int N = 100000;
const int K = N;
const int M = 100000;
const int MOD = 666013;

int n, k, m;
int v[N];
query_int q[M];
int last[K+1];
long long aib[N+1];

bool comp_interval ( const query_int &a, const query_int &b ) { return (a.f == b.f) ? a.s < b.s : a.f < b.f; }
bool comp_orig_poz ( const query_int &a, const query_int &b ) { return a.orig_poz < b.orig_poz; }

int lsb ( int a ) { return (a & (a-1))^a; }

void add ( int p, int v ) {
	for (int x = p; x <= n; x += lsb(x))
		aib[x] = aib[x] + v;
}

long long query ( int p ) {
	long long rez = 0;
	for (int x = p; x; x -= lsb(x))
		rez = (rez + aib[x]) % MOD;
	return rez;
}

int main() {
	freopen("distincte.in","rt",stdin);
	freopen("distincte.out","wt",stdout);
	scanf("%d %d %d",&n,&k,&m);
	for (int i = 0; i < n; ++i) scanf("%d",&v[i]);
	for (int i = 0; i < m; ++i) {
		scanf("%d %d",&q[i].s,&q[i].f);
		q[i].orig_poz = i;
	}

	sort(q,q+m,comp_interval);
	
	int q_ptr = 0;
	for (int i = 0; i < n; ++i) {
		add(i+1, v[i]);
		if (last[v[i]])
			add(last[v[i]], -v[i]);
		last[v[i]] = i+1;

		for (; q_ptr < m && q[q_ptr].f == i+1; ++q_ptr) {
			q[q_ptr].rez = query(q[q_ptr].f) - query(q[q_ptr].s-1);
			if (q[q_ptr].rez < 0) q[q_ptr].rez += MOD;
		}
	}

	sort(q,q+m,comp_orig_poz);
	for (int i = 0; i < m; ++i)
		printf("%lld\n",q[i].rez);
	return 0;
}