#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

struct query_int {
	int s, f, orig_poz;
	int rez;
};

const int N = 100000;
const int K = N;
const int M = 100000;
//const int AINT_SIZE = 1 << 18;
const int MOD = 666013;

int n, k, m;
int v[N];
query_int q[M];
int last[K+1];
//int top_length;
//int ai[AINT_SIZE];
int aib[N+1];

inline int mod ( int a, int b = MOD ) {
	if (a < 0)
		return a += ((int)fabs((double)a) / b + 1) * b; else
		return a -= ((int)fabs((double)a) / b) * b;
}

bool comp_interval ( const query_int &a, const query_int &b ) { return (a.f == b.f) ? a.s < b.s : a.f < b.f; }
bool comp_orig_poz ( const query_int &a, const query_int &b ) { return a.orig_poz < b.orig_poz; }

/* void add ( int node, int node_start, int node_length, int target, int value ) {
	ai[node] = (ai[node] + value) % MOD;
	if (node_length > 1)
		if (target < node_start + (node_length >> 1))
			add(node*2+1, node_start, node_length >> 1, target, value); else
			add(node*2+2, node_start + (node_length >> 1), node_length >> 1, target, value);
}

int query ( int node, int node_start, int node_length, int target_start, int target_end ) {
	if (target_start == node_start && target_end == node_start + node_length - 1)
		return ai[node];
	int mid = node_start + (node_length >> 1);
	int r = 0;
	if (target_start < mid)
		r += query(node*2+1, node_start, node_length >> 1, target_start, min(target_end, mid-1));
	if (target_end >= mid)
		r += query(node*2+2, mid, node_length >> 1, max(target_start, mid), target_end);
	return r%MOD;
} */

int lsb ( int a ) { return (a & (a-1))^a; }

void add ( int p, int v ) {
	for (int x = p; x <= n; x += lsb(x))
		aib[x] = mod(aib[x] + v);
}

int query ( int p ) {
	int rez = 0;
	for (int x = p; x; x -= lsb(x))
		rez = mod(rez + aib[x]);
	return rez;
}

int main() {
	freopen("distincte.in","rt",stdin);
	freopen("distincte.out","wt",stdout);
	scanf("%d %d %d",&n,&k,&m);
	for (int i = 0; i < n; ++i) scanf("%d",&v[i]);
	for (int i = 0; i < m; ++i) {
		scanf("%d %d",&q[i].s,&q[i].f);
		q[i].orig_poz = i;
	}

	sort(q,q+m,comp_interval);
	
	for (int i = 1; i <= k; ++i) last[i] = -1;
	int query_ptr = 0;
	for (int i = 0; i < n; ++i) {
		add(i+1, v[i]);
		if (last[v[i]] != -1)
			add(last[v[i]], -v[i]);
		last[v[i]] = i+1;

		for (; query_ptr < m && q[query_ptr].f == i+1; ++query_ptr)
			q[query_ptr].rez = query(q[query_ptr].f) - query(q[query_ptr].s-1);
	}

	sort(q,q+m,comp_orig_poz);
	for (int i = 0; i < m; ++i)
		printf("%d\n",q[i].rez);
	return 0;
}