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

using namespace std;

struct QUERY{
	int x, y, o;
} Q[MAXN];

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

inline bool cmp(QUERY a, QUERY b) { return a.y < b.y; }
inline bool cmp2(QUERY a, QUERY b) { return a.o < b.o; }

void Update(int p, int x){
	for (; p <= N; p += zeros(p))
		BIT[p] += x,
		BIT[p] %= MOD;
}

int Query(int p){
	int ans = 0;
	for (; p; p -= zeros(p))
		ans += BIT[p],
		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].x, &Q[i].y),
		Q[i].o = i;

	sort(Q + 1, Q + M + 1, cmp);
	
	for (int i = 1; i <= M; ++i){
		for (int j = Q[i - 1].y + 1; j <= Q[i].y; ++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].y) - Query(Q[i].x - 1);
	}
	for (int i = 1; i <= M; ++i)
		printf("%d\n", sol[i]);

	return 0;
}