#include <fstream>
#include <algorithm>

using namespace std;

#define MAX_N 100005
#define MOD 666013

ifstream fin ("distincte.in");
ofstream fout ("distincte.out");

struct query{int x, y;} Q[MAX_N];

int K, N, M, A[MAX_N], V[MAX_N], I[MAX_N], Ant[MAX_N], Sol[MAX_N];

struct cmp
{
	bool operator() (const int &a, const int &b)
	{
		return Q[a].y < Q[b].y;
	}
};

inline int lsb(const int &x)
{
	return (x & -x);
}

void citire()
{
	fin >> N >> K >> M;	

	for(int i = 1; i <= N; ++i)
	{
		fin >> V[i];
		Ant[i] = N+1;
	}

	for(int i = 1; i <= M; ++i)
	{
		fin >> Q[i].x >> Q[i].y;
		I[i] = i;
	}

	sort(I+1, I+M+1, cmp());
}

void update(int poz, int val)
{
	for(; poz <= N; poz += lsb(poz))
	{
		A[poz] += val;
		A[poz] %= MOD;
		if(A[poz] < 0)
			A[poz] += MOD;
	}
}

int sum(int poz)
{
	int sum = 0;
	for(; poz; poz -= lsb(poz))
	{
		sum += A[poz];
		sum %= MOD;
	}
	return sum;
}

void solve()
{
	int j = 1;

	for(int i = 1; i <= N; ++i)
	{
		update(Ant[V[i]], -V[i]);
		update(i, V[i]);
		Ant[V[i]] = i;

		while(Q[I[j]].y == i)
		{
			Sol[I[j]] = sum(Q[I[j]].y) - sum(Q[I[j]].x - 1);
			if(Sol[I[j]] < 0) Sol[I[j]] += MOD;
			++j;
		}	
	}

	for(int i = 1; i <= M; ++i)
		fout << Sol[i] << "\n";
}

int main()
{
	citire();
	solve();
}