#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int N = 1e5 + 5;
const int modulo = 666013;

int n;
int v[N];

vector<pair<int, int>> q[N];		// q[b] = { a, index }

long arbore[4 * N];
long ans[N];
int last[N]; // last[i] = ultima pozitie pe care apare valoarea i

void updateNode(int poz, int val, int tl = 1, int tr = n, int ti = 1) // functia face update la nodul cu indexul ti
{
	if (tl == tr) // daca am ajuns la o frunza
	{
		arbore[ti] = val; // actualizez valoarea
		return;
	}

	int mid = (tl + tr) / 2; // mijlocul intervalului

	if (poz <= mid) // daca pozitia se afla in prima jumatate
	{
		updateNode(poz, val, tl, mid, ti * 2); // actualizez nodul din stanga
	}
	else
	{
		updateNode(poz, val, mid + 1, tr, ti * 2 + 1); // actualizez nodul din dreapta
	}

	arbore[ti] = arbore[ti * 2] + arbore[ti * 2 + 1]; // actualizez valoarea nodului curent
}

long query(int ql, int qr, int tl = 1, int tr = n, int ti = 1) // functia returneaza suma elementelor din intervalul [ql, qr]
{
	if (ql <= tl && tr <= qr) // daca intervalul nodului curent este inclus in intervalul cautat
	{
		return arbore[ti]; // returnez valoarea nodului curent
	}

	int mid = (tl + tr) / 2; // mijlocul intervalului
	if (qr <= mid) // daca intervalul cautat se afla in prima jumatate
	{
		return query(ql, qr, tl, mid, ti * 2); // returnez suma elementelor din intervalul [ql, qr] din nodul din stanga
	}
	else if (ql > mid) // daca intervalul cautat se afla in a doua jumatate
	{
		return query(ql, qr, mid + 1, tr, ti * 2 + 1); // returnez suma elementelor din intervalul [ql, qr] din nodul din dreapta
	}
	else
	{
		return query(ql, qr, tl, mid, ti * 2) + query(ql, qr, mid + 1, tr, ti * 2 + 1); // returnez suma elementelor din intervalul [ql, qr] din nodul din stanga si din dreapta
	}
}

int main()
{
	int k, m;
	f >> n >> k >> m;

	for (int i = 1; i <= n; i++)
	{
		f >> v[i];
	}

	for (int i = 1; i <= m; i++)
	{
		int a, b;
		f >> a >> b;

		q[b].push_back({ a, i });
	}

	for (int i = 1; i <= n; i++)
	{
		updateNode(i, v[i]);

		if (last[v[i]])
		{
			updateNode(last[v[i]], 0);
		}

		last[v[i]] = i;

		for (auto val : q[i]) // val = { a, index }
		{
			ans[val.second] = query(val.first, i); // val.first = a, i = b
		}
	}

	for (int i = 1; i <= m; i++)
	{
		g << ans[i] % modulo << '\n';
	}
}