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

using namespace std;

#define nm 100100
#define mm 350100
#define mod 666013

struct interv
{
	int x, y;
};

int n, k, m, a[nm], c[mm], p[nm], sol[nm], used[nm], tmp;
interv v[nm];

int cmp(int a, int b)
{
	return v[a].y < v[b].y;
}

void add(int pos, int val)
{
	used[val] = pos - tmp + 1;

	while(pos)
	{
		c[pos] += val;

		if (c[pos] >= mod)
			c[pos] -= mod;
		if (c[pos] < 0)
			c[pos] += mod;

		pos >>= 1;
	}
}

int querry(int nod, int st, int dr, int x, int y)
{
	if (st == x && dr == y)
		return c[nod];

	if (dr <= (x + y) / 2)
		return querry(nod * 2, st, dr, x, (x + y) / 2);
	if (st > (x + y) / 2)
		return querry(nod * 2 + 1, st, dr, (x + y) / 2 + 1, y);
	return querry(nod * 2, st, (x + y) / 2, x, (x + y) / 2) + querry(nod * 2 + 1, (x + y) / 2 + 1, dr, (x + y) / 2 + 1, y);
}

int main()
{
	int i, j;

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

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

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

	for (i = 1; i <= m; ++i)
	{
		scanf("%d%d", &v[i].x, &v[i].y);
		p[i] = i;
	}

	sort(p + 1, p + m + 1, cmp);

	for (tmp = 1; tmp < n; tmp <<= 1);

	for (i = 1, j = 1; i <= m; ++i)
	{
		for (; j <= v[p[i]].y; ++j)
		{
			if (used[a[j]])
				add(tmp - 1 + used[a[j]], -a[j]);
			add(tmp - 1 + j, a[j]);
		}

		sol[p[i]] = querry(1, v[p[i]].x, v[p[i]].y, 1, tmp);
	}

	for (i = 1; i <= m; ++i)
		printf("%d\n", sol[i]);
}