#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

const int kMaxN = 100005, kMod = 666013;

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

int N, K, M, a[kMaxN], last[kMaxN];
int aib[kMaxN], sol[kMaxN];

vector<pair<int, int>> q[kMaxN];

void Update(int pos, int val) {
	for (int i = pos; i <= N; i += i & (-i))
		aib[i] = (aib[i] + val + kMod) % kMod;
}

int Query(int pos) {
	int ans = 0;
	for (int i = pos; i; i -= i & (-i))
		ans = (ans + aib[i]) % kMod;
	return ans;
}
int Query(int l, int r) {
	return Query(r) - Query(l - 1);
}

int main() {
	fin >> N >> K >> M;
	for (int i = 1; i <= N; ++i)
		fin >> a[i];
	for (int i = 0; i < M; ++i) {
		int l, r;
		fin >> l >> r;
		q[r].push_back(make_pair(i, l));
	}
	for (int i = 1; i <= N; ++i) {
		if (last[a[i]])
			Update(last[a[i]], -a[i]);
		Update(i, a[i]);
		last[a[i]] = i;
		for (auto it : q[i])
			sol[it.first] = Query(it.second, i);
	}
	for (int i = 0; i < M; ++i)
		fout << sol[i] << "\n";
	return 0;
}