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

#define pb push_back

const string filename = "distincte";

ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

const int mod = 666013;

int n, m, k;
int a[100005], prevv[100005], aib[100005], ans[100005];


struct qrys
{
	int st, dr, ind;
	bool operator <(const qrys &oth)const
	{
		return dr < oth.dr;
	}
} q[100005];

void upd(int i, int val)
{
	for (; i <= n; i += (i & (-i)))
	{
		aib[i] += val;
		if (aib[i] >= mod) aib[i] -= mod;
		if (aib[i] < 0) aib[i] += mod;
	}
}

int qry(int i)
{
	int s = 0;
	for (; i > 0; i -= (i & (-i)))
	{
		s += aib[i];
		if (s >= mod) s -= mod;
	}
	return s;
}

int main()
{

	fin >> n >> k >> m;
	for (int i = 1; i <= n; ++i)
		fin >> a[i];
	for (int i = 1; i <= m; ++i)
	{
		fin >> q[i].st >> q[i].dr;
		q[i].ind = i;
	}
	sort(q + 1, q + m + 1);

	int p = 1;
	for (int i = 1; i <= n; ++i)
	{
		upd(i, a[i]);
		if (prevv[a[i]])
			upd(prevv[a[i]], -a[i]);
		while (p <= m && q[p].dr == i)
		{
			ans[q[p].ind] = qry(q[p].dr) - qry(q[p].st - 1);
			if (ans[q[p].ind] < 0)
				ans[q[p].ind] += mod;
			p++;
		}
		prevv[a[i]] = i;
	}
	for (int i = 1; i <= m; ++i)
		fout << ans[i] << '\n';

	fin.close();
	fout.close();
	return 0;
}