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

#define ll long long

using namespace std;

ifstream fin("distincte.in");
ofstream fout("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 }

ll arbore[4 * N];
ll ans[N];
int last[N];

void updateNode(int poz, int val, int tl = 1, int tr = n, int ti = 1)
{
	if (tl == tr)
	{
		arbore[ti] = val;
		return;
	}

	int mid = (tl + tr) / 2;

	if (poz <= mid)
	{
		updateNode(poz, val, tl, mid, ti * 2);
	}
	else
	{
		updateNode(poz, val, mid + 1, tr, ti * 2 + 1);
	}

	arbore[ti] = arbore[ti * 2] + arbore[ti * 2 + 1];
}

ll query(int ql, int qr, int tl = 1, int tr = n, int ti = 1)
{
	if (ql <= tl && tr <= qr)
	{
		return arbore[ti];
	}

	int mid = (tl + tr) / 2;
	if (qr <= mid)
	{
		return query(ql, qr, tl, mid, ti * 2);
	}
	else if (ql > mid)
	{
		return query(ql, qr, mid + 1, tr, ti * 2 + 1);
	}
	else
	{
		return query(ql, qr, tl, mid, ti * 2) + query(ql, qr, mid + 1, tr, ti * 2 + 1);
	}
}

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

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

	for (int i = 1; i <= m; i++)
	{
		int a, b;
		fin >> 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])
		{
			ans[val.second] = query(val.first, i);
		}
	}

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