#include <fstream>
#include <algorithm>

using namespace std;

typedef struct
{
	int x;
	int y;
	int ind;
} dog;

#define lsb(x) (x & -x)
#define mod 666013
int N, K, M;
dog QQ[100011];
int Aib[100011];
int v[100011];
int found[100011];
int next[100011];

void Update (int i, int val)
{
	for (; i <= N; i += lsb (i))
	{
		Aib[i] += val;
		if (Aib[i] < 0) Aib[i] += mod;
		if (Aib[i] >= mod) Aib[i] -= mod;
	}
}

int Query (int i)
{
	int S = 0;
	for (; i; i -= lsb (i))
	{
		S += Aib[i];
		if (S >= mod) S -= mod;
	}
	return S;
}

void Citire ()
{
	ifstream fin ("distincte.in");
	fin >> N >> K >> M;
	for (int i = 1; i <= N; i++)
	{
		fin >> v[i];
		if (!found[v[i]]) Update (i, v[i]);
		else next[found[v[i]]] = i;
		found[v[i]] = i;
	}
	for (int i = 1; i <= N; i++)
		if (next[i] == 0) next[i] = N + 1;
	for (int i = 0; i < M; i++)
	{
		fin >> QQ[i].x >> QQ[i].y;
		QQ[i].ind = i;
	}
	fin.close ();
}

inline int cmp (dog a, dog b)
{
	if (a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}

void Business ()
{
	sort (QQ, QQ + M, cmp);
	int i = 1, a;
	for (int j = 0; j < M; j++)
	{
		for (; i < QQ[j].x; i++)
		{
			Update (i, -v[i]);
			Update (next[i], v[i]);
		}
		a = Query (QQ[j].y) - Query (QQ[j].x - 1);
		if (a >= mod) a -= mod;
		if (a < 0) a += mod;
		found[QQ[j].ind] = a;
	}
}

void Scriere ()
{
	ofstream fout ("distincte.out");
	for (int i = 0; i < M; i++)
		fout << found[i] << "\n";
	fout.close ();
}

int main ()
{
	Citire ();
	Business ();
	Scriere ();
	return 0;
}