#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define MAXN 100005
#define MOD 666013
#define zeros(x) (x & -x)

using namespace std;

struct Queries{
	int i, j, o;
} Q[MAXN];

int N, K, M, BIT[MAXN], v[MAXN], used[MAXN], sol[MAXN];

inline int cmp(Queries a, Queries b){ return a.j < b.j; }

void update(int idx, int val){
	for (; idx <= N; idx += zeros(idx))
		BIT[idx] += val + MOD,
		BIT[idx] %= MOD;
	
}

int query(int idx){
	int ans = 0;
	for (; idx > 0; idx -= zeros(idx))
		ans += BIT[idx],
		ans %= MOD;
	return ans;
}

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

	scanf("%d %d %d", &N, &K, &M);

	for (int i = 1; i <= N; ++i)
		scanf("%d", &v[i]);

	for (int i = 1; i <= M; ++i)
		scanf("%d %d", &Q[i].i, &Q[i].j),
		Q[i].o = i;
	sort(Q + 1, Q + M + 1, cmp);

	for (int i = 1; i <= M; ++i){
		for (int j = Q[i - 1].j + 1; j <= Q[i].j; ++j){
			if (used[v[j]])
				update(used[v[j]], -v[j]);
			update(j, v[j]);
			used[v[j]] = j;
		}
		sol[Q[i].o] = ((query(Q[i].j)- query(Q[i].i - 1)) + MOD) % MOD;
	}
	for (int i = 1; i <= M; ++i)
		printf("%d\n", sol[i]);

	return 0;
}