#include <fstream>
#include <vector>

using namespace std;

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

int n, k,m;
vector<int>v, last;
vector<long long>rez,aib;
vector<vector<pair<int, int>>>queries;

long long query(int pos) {
	long long sum = 0;
	for(int i=pos; i>0; i-=i&(-i))
	{
		sum += aib[i];
	}
	return sum;
}

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

int main()
{
	in >> n >> k >> m;
	v.resize(n + 1);
	aib.resize(n + 1);
	queries.resize(n + 1);
	last.resize(100001);
	rez.resize(m + 1);
	for(int i=1; i<=n; i++)
	{
		in >> v[i];
	}
	for(int i=1;i<=m;i++) {
		int x, y;
		in >> x >> y;
		queries[y].push_back({ x, i });
	}
	for (int i = 1; i <= n; i++) {
		if (last[v[i]] == 0) {
			last[v[i]] = i;
			update(i, v[i]);
		}
		else {
			update(last[v[i]], -v[i]);
			last[v[i]] = i;
			update(i, v[i]);
		}
		for(auto it : queries[i]) {
			int x = it.first;
			int pos = it.second;
			int ans = query(i) - query(x - 1);
			rez[pos] = ans;
		}
	}
	for(int i=1; i<=m; i++)
	{
		out << rez[i] % 666013 << "\n";
	}
}