#include <bits/stdc++.h>

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

const int NMAX = 1e5;
const int MMAX = 1e5;
const int KMAX = 1e5;
const int MOD = 666013;

struct Query {
	int le, ri, id;
	Query() {}
	Query(int le, int ri, int id) : le(le), ri(ri), id(id) {}
	bool operator < (const Query &oth) const {
		return ri < oth.ri;
	}
};

int n, k, m;
int v[NMAX + 1];
Query queries[MMAX + 1];
int lastPos[KMAX + 1];
int ans[MMAX + 1];

void addSelf(int &x, int y) {
	x += y;
	if(x >= MOD) {
		x -= MOD;
	}
	if(x < 0) {
		x += MOD;
	}
}

int add(int x, int y) {
	addSelf(x, y);
	return x;
}

int aib[NMAX + 1];

int lsb(int i) {
	return i & (-i);
}

void update(int pos, int val) {
	for(int i = pos; i <= n; i += lsb(i)) {
		addSelf(aib[i], val);
	}
}

int query(int pos) {
	int ret = 0;
	for(int i = pos; i > 0; i -= lsb(i)) {
		addSelf(ret, aib[i]);
	}
	return ret;
}

int query(int le, int ri) {
	return add(query(ri), -query(le - 1));
}

int main() {
	ios_base :: sync_with_stdio(false);

	fin >> n >> k >> m;
	for(int i = 1; i <= n; i++) {
		fin >> v[i];
	}
	for(int i = 1; i <= m; i++) {
		int le, ri;
		fin >> le >> ri;
		queries[i] = Query(le, ri, i);
	}

	sort(queries + 1, queries + m + 1);

	for(int i = 1, pos = 1; i <= m; i++) {
		while(pos <= queries[i].ri) {
			if(lastPos[v[pos]] == 0) {
				update(pos, v[pos]);
				lastPos[v[pos]] = pos;
			} else {
				update(lastPos[v[pos]], -v[pos]);
				update(pos, v[pos]);
				lastPos[v[pos]] = pos;
			}
			pos++;
		}
		ans[queries[i].id] = query(queries[i].le, queries[i].ri);
	}

	for(int i = 1; i <= m; i++) {
		fout << ans[i] << '\n';
	}

	fin.close();
	fout.close();
	return 0;
}