#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

#define ll long long

using namespace std;

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


struct query {

	int l, r, idx;

};


vector<ll> aib;
vector<int> v;
vector<int> ante;
vector<int> ans;
vector<query> queries;
int n, k, q;

void update(int i, int val) {

	for (; i <= n; i+=(i & (-i))) {
		aib[i] += val;
	}

}

ll take(int i) {

	ll sum = 0;
	for (; i > 0; i-=(i & (-i))) {
		sum += aib[i];
	}

	return sum;

}


bool cmp(query a, query b) {

	return a.r < b.r;

}


int main() {

	fin >> n >> k >> q;

	aib.resize(n + 2);
	v.resize(n + 2);
	ante.resize(k + 2);
	ans.resize(q);
	queries.resize(q);

	for (int i = 1; i <= n; i++) {
		fin >> v[i];
	}

	for (int i = 0; i < q; i++) {

		fin >> queries[i].l >> queries[i].r;
		queries[i].idx = i;

	}

	sort(queries.begin(), queries.end(), cmp);

	int j = 0;

	for (int i = 0; i < n; i++) {

		j++;

		if (ante[v[j]] != 0) {
			update(ante[v[j]], -v[j]);
		}

		update(j, v[j]);

		ante[v[j]] = j;

		while (i < q && queries[i].r == j) {

			int l = queries[i].l;
			int r = queries[i].r;
			int idx = queries[i].idx;

			ans[idx] = (take(r) - take(l - 1)) % 666013;

			i++;

		}

	}

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

	return 0;
}