#include <bits/stdc++.h>
using namespace std;

const int nmax = 1 << 18;
int ai[nmax];
const int mod = 666013;
void update(int nod, int left, int right, int index, int val)
{
	if(left == right)
	{
		ai[nod] += val;
		ai[nod] %= mod;
		return;
	}
	int mid = (left + right) / 2;
	if(index <= mid)
		update(2 * nod + 1, left, mid, index, val);
	else
		update(2 * nod + 2, mid + 1, right, index, val);
	ai[nod] = ai[2 * nod + 1] + ai[2 * nod + 2];
	ai[nod] %= mod;
}

int query(int nod, int left, int right, int L, int R)
{
	if(L <= left && right <= R)
		return ai[nod];
	if(L > right || R < left)
		return 0;
	int mid = (left + right) / 2;
	return (query(2 * nod + 1, left, mid, L, R) + query(2 * nod + 2, mid + 1, right, L, R)) % mod;
}


int main() {
	freopen("distincte.in", "r", stdin);
	freopen("distincte.out", "w", stdout);
	int n, k, m;
	cin >> n >> k >> m;
	vector<int> v(n);
	for(int i = 0;i < n;++i)
		cin >> v[i];
	vector<pair<int,int>> q[n];
	vector<int> ans(m);
	
	for(int i = 0;i < m;++i)
	{
		int a, b;
		cin >> a >> b;
		--a, --b;
		q[b].push_back({a, i});
	}
	int prev[k + 1];
	memset(prev, -1, sizeof(prev));
	memset(ai, 0, sizeof(ai));
	for(int i = 0;i < n;++i)
	{
		if(prev[v[i]] != -1)
			update(0, 0, n - 1, prev[v[i]], -v[i]);
		update(0, 0, n - 1, i, v[i]);
		prev[v[i]] = i;
		vector<pair<int,int>>& tmp = q[i];
		for(size_t j = 0;j < tmp.size();++j)
		{
			int ret = query(0, 0, n - 1, tmp[j].first, i);
			ans[tmp[j].second] = ret;
		}
	}
	for(int i = 0;i < m;++i)
		cout << ans[i] << "\n";
}