#include <cstdio>
using namespace std;

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

#define MAX_N 100007

int N, K, M;

int A[MAX_N];

int cnt[MAX_N];


int main(void)
{
	freopen(iname, "r", stdin);
	scanf("%d", & N);
	scanf("%d", & K);
	scanf("%d", & M);
	for (int i = 1; i <= N; ++ i)
		scanf("%d", A + i);

	freopen(oname, "w", stdout);
	for (; M --; ) {
		int a;
		int b;
		scanf("%d %d", & a, & b);
		int sum = 0;
		for (int i = a; i <= b; ++ i) {
			if (cnt[A[i]] == 0) sum = (sum + A[i]) % 666013;
			cnt[A[i]] ++;
		}
		for (int i = a; i <= b; ++ i)
			cnt[A[i]] --;
		printf("%d\n", sum);
	}
	return 0;
}