#include <algorithm>
#include <stdio.h>

#define MAX 100010
#define restRez 666013
#define bit(x) (x & (x ^ (x - 1)))
#define ll long long
#define mp make_pair
#define f first
#define s second

using namespace std;

int n, k, m;
int a[MAX], urm[MAX], ap[MAX];
ll sum[MAX], sol[MAX];
ll aiSum[4 * MAX];
pair <pair <int, int>, int> q[MAX];

inline void addAi(int nod, int st, int fn, int loc, ll val)
{
	if (st == fn)
	{
		aiSum[nod] += val;

		return;
	}
	
	int med = (st + fn) / 2;
	if (loc <= med)
		addAi(nod * 2, st, med, loc, val);
	else addAi(nod * 2 + 1, med + 1, fn, loc, val);

	aiSum[nod] = aiSum[nod * 2] + aiSum[nod * 2 + 1];
}

inline ll queryAi(int nod, int st, int fn, int qs, int qf)
{
	if (qs <= st && fn <= qf)
		return aiSum[nod];

	int med = (st + fn) / 2;
	ll rez = 0;
	if (qs <= med)
		rez += queryAi(nod * 2, st, med, qs, qf);
	if (med < qf)
		rez += queryAi(nod * 2 + 1, med + 1, fn, qs, qf);

	return rez;
}

int main()
{
	freopen("distincte.in", "r", stdin);
	freopen("distincte.out", "w", stdout);

	scanf("%d %d %d", &n, &k, &m);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);

		sum[i] = sum[i - 1];
		if (!ap[a[i]])
			sum[i] = sum[i] + a[i];

		ap[a[i]] = i;
	}

	for (int i = 1; i <= n; i++)
		ap[i] = n + 1;
	for (int i = n; i; i--)
	{
		urm[i] = ap[a[i]];
		
		ap[a[i]] = i;
	}

	for (int i = 1; i <= m; i++)
	{
		scanf("%d %d\n", &q[i].f.f, &q[i].f.s);

		q[i].s = i;
	}

	sort(q + 1, q + 1 + m);

	int r = 1;
	for (int i = 1; i <= m; i++)
	{
		for (; r < q[i].f.f; r++)
			addAi(1, 1, n + 1, urm[r], a[r]);

		sol[q[i].s] = sum[q[i].f.s] - queryAi(1, 1, n + 1, q[i].f.s + 1, n + 1);
	}

	for (int i = 1; i <= m; i++)
		printf("%lld\n", sol[i] % restRez);

	fclose(stdin);
	fclose(stdout);
	return 0;
}