#include <stdio.h>
#include <vector>
#include <algorithm>

#define mij (((st) + (dr)) / 2)
#define fiu1 ((nod) * 2)
#define fiu2 (((nod) * 2) + 1)

const int N_MAX = 100010;
const int A_MAX = 1 << 18;
const int MOD = 666013;

using namespace std;

int N, K, M;
int v[N_MAX], aint[A_MAX], last[N_MAX];
pair <pair <int, int>, int> qr[N_MAX];
pair <int, int> rez[N_MAX];

void constr(int nod, int st, int dr)
{
	if (st == dr) aint[nod] = v[st] % MOD;
	else {
		constr(fiu1, st, mij);
		constr(fiu2, mij + 1, dr);
		aint[nod] = ((aint[fiu1] % MOD) + (aint[fiu2] % MOD)) % MOD;
	}
}

int cmp(pair <pair <int, int>, int> a, pair <pair <int, int>, int> b)
{
	if (a.first.second != b.first.second) return (a.first.second < b.first.second);
	else return (a.first.first < b.first.first);
}

void update(int nod, int st, int dr, int poz, int val)
{
	if (st == dr) aint[nod] = val % MOD;
	else {
		if (poz <= mij) update(fiu1, st, mij, poz, val);
		if (poz > mij) update(fiu2, mij + 1, dr, poz, val);

		aint[nod] = ((aint[fiu1] % MOD) + (aint[fiu2] % MOD)) % MOD;
	}
}

int query(int nod, int st, int dr, int a, int b)
{
	if (a <= st && dr <= b) return aint[nod];
	else {
		int sum = 0;
		if (a <= mij) sum += query(fiu1, st, mij, a, b) % MOD;
		sum = sum % MOD;
		if (b > mij) sum += query(fiu2, mij + 1, dr, a, b) % MOD;
		sum = sum % MOD;
		
		return sum;
	}
}

int main()
{
	freopen("distincte.in", "r", stdin);
#ifndef _SCREEN_
	freopen("distincte.out", "w", stdout);
#endif

	scanf("%d %d %d\n", &N, &K, &M);
	for (int i = 1; i <= N; i ++) {
		scanf("%d\n", &v[i]);
	}

	constr(1, 1, N);

	int x, y;
	for (int i = 1; i <= M; i ++) {
		scanf("%d %d\n", &x, &y);
		qr[i] = make_pair(make_pair(x, y), i);
	}
	sort(qr + 1, qr + M + 1, cmp);

	int poz = 1;
	for (int i = 1; i <= M; i ++) {
		int inc = qr[i].first.first, sf = qr[i].first.second;

		for (int j = poz; j <= sf; j ++) {
			if (last[v[j]]) update(1, 1, N, last[v[j]], 0);
			last[v[j]] = j;
		}
		poz = sf + 1;

		rez[i] = make_pair(qr[i].second, query(1, 1, N, inc, sf));
	}

	sort(rez + 1, rez + M + 1);
	for (int i = 1; i <= M; i ++) printf("%d\n", rez[i].second);

	return 0;
}