#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

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

int n, m, k, block_size, L = 1, R = 0;
long long sumcurr;
vector<long long>a,freq,rez;
struct Query
{
	int x, y, idx;
	bool operator<(const Query& other) const
	{
		int block_a = x / block_size;
		int block_b = other.x / block_size;
		if (block_a != block_b)
			return block_a < block_b;
		return y < other.y;
	}
};
vector<Query> queries;

int main()
{
	in >> n >> k >> m;
	block_size = static_cast<int>(sqrt(n));
	a.resize(100001);
	freq.resize(100001,0);
	rez.resize(100001,0);
	for (int i = 1; i <= n; ++i)
		in >> a[i];
	for (int i = 1; i <= m; ++i)
	{
		Query query;
		in >> query.x >> query.y;
		query.idx = i-1;
		queries.push_back(query);
	}
	sort(queries.begin(), queries.end());
	for(auto query : queries)
	{
		int l = query.x;
		int r = query.y;
		long long val;
		while (R<r)
		{
			R++;
			val = a[R];
			freq[val]++;
			if (freq[val] == 1)
				sumcurr = sumcurr + val;
		}
		while (R>r)
		{
			val = a[R];
			freq[val]--;
			if(freq[val] == 0)
				sumcurr = sumcurr - val;
			R--;
		}
		while (L<l)
		{
			val = a[L];
			freq[val]--;
			if (freq[val] == 0)
				sumcurr = sumcurr - val;
			L++;
		}
		while (L>l)
		{
			L--;
			val = a[L];
			freq[val]++;
			if(freq[val] == 1)
				sumcurr = sumcurr + val;
		}
		rez[query.idx] = sumcurr%666013;
	}
	for (int i = 0; i < m; ++i)
		out << rez[i] << "\n";
	return 0;
}