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

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

const int N = 100000;
const int K = N;
const int M = 100000;
const int MOD = 666013;

int n, k, m;
int v[N];
query_int q[M];
int last[K+1];
long long aib[N+1];

template <class T> inline T mod ( T a, T 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; }

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);
}

long long query ( int p ) {
	long long 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("%lld\n",q[i].rez);
	return 0;
}