#include <cstdio>
#include <memory>
using namespace std;

const char iname[] = "distincte.in";
const char oname[] = "distincte.out";

#define MAX_N  100007
#define MAX_R  317
#define modulo 666013
#define min(z, w) ((z) < (w) ? (z) : (w))

int N, K, M;

unsigned int L[7][MAX_R][MAX_R];

int grup[7][MAX_N];

int num[7];

int sqr[7];

int lim;

int A[MAX_N];

int rad(const int n) {
	int i;
	for (i = 1; i * i <= n; ++ i) ;
	return i;
}

void print(unsigned int A[], int n)
{
	for (int i = 0; i <= rad(n); ++ i)
		for (int j = 0; j < 32; ++ j)
			if (A[i] & 1 << j)	printf("%d ", j);
	printf("\n");
}

int main(void)
{
	freopen(iname, "r", stdin);
	scanf("%d", & N);
	scanf("%d", & K);
	scanf("%d", & M);
	for (int i = 0; i < N; ++ i) {
		scanf("%d", A + i);
		L[0][i][A[i] >> 5] |= 1 << (A[i] & 31);
		grup[0][i] = i;
	}
	lim = K / 32 + 1;
	
	num[0] = N;
	sqr[0] = 1;
	int level;
	for (level = 1; level < 7; ++ level) {
		sqr[level] = rad(num[level - 1]);
		int cnt = 0;
		for (int i = 0; i < num[level - 1]; i += sqr[level], ++ cnt) {
			int j = min(i + sqr[level], num[level - 1]);
			for (int k = i; k < j; ++ k) {
				for (int depl = 0; depl <= lim; ++ depl)
					L[level][cnt][depl] |= L[level - 1][k][depl];
			}
		}
		int size = N / cnt;
		if (size * cnt < N)  size ++ ;
		int numar = 0;
		for (int i = 0; i < N; i += size, ++ numar) {
			int j  = min(i + size, N);
			for (int k = i; k < j; ++ k)
				grup[level][k] = numar;
		}

		num[level] = cnt;
		if (num[level] == 1)
			break ;
	}

	int lo;
	int hi;
	int V[MAX_R] = {0};
	freopen(oname, "w", stdout);
	for (; M --; ) {
		scanf("%d %d", & lo, & hi);
		lo --, hi --;
	
		for (int k = level; k > 0; -- k)
			if (grup[k][lo] < grup[k][hi])	break ;

		for (int n = grup[k][lo] + 1; n < grup[k][hi]; ++ n) {
			for (int i = 0; i <= lim; ++ i)
				V[i] |= L[k][n][i];
		}
		for (int i = lo; i < N  && grup[k][lo] == grup[k][i]; ++ i)
			V[A[i] >> 5] |= 1 << (A[i] & 31);
		for (int i = hi; i >= 0 && grup[k][hi] == grup[k][i]; -- i)
			V[A[i] >> 5] |= 1 << (A[i] & 31);

		int sum = 0;
		for (int i = 0; i <= lim; ++ i)
			for (int j = 0; j < 32; ++ j)
				if (V[i] & 1 << j)	sum = (sum + j) % modulo;
		memset(V, 0, sizeof(V));
		printf("%d\n", sum);
	}		
	return 0;
}