#include <fstream>
#include <algorithm>

using namespace std;

const int MOD = 666013;

int N, K, M;
int A[100002], next[100002], last[100002], posA[100002];
int Left[100002], Right[100002], pos[100002];
int AIB[100002], result[100002];

void update(int pos, int val)
{
	for (; pos <= N; pos += pos & -pos)
	{
		AIB[pos] += val;
		if (AIB[pos] >= MOD) AIB[pos] -= MOD;
	}
}
long long query(int pos)
{
	long long sum = 0;
	for (; pos >= 1; pos -= pos & -pos)
	{
		sum += AIB[pos];
		if (sum >= MOD) sum -= MOD;
	}
	return sum;
}

inline bool compareA(const int& i1, const int& i2)
{
	return next[i1] > next[i2];
}
inline bool compare(const int& i1, const int& i2)
{
	return Right[i1] > Right[i2];
}

int main()
{
	ifstream fin("distincte.in");
	ofstream fout("distincte.out");
	
	fin >> N >> K >> M;
	for (int i = 1; i <= N; ++i)
		fin >> A[i];
	for (int i = 1; i <= M; ++i)
	{
		fin >> Left[i] >> Right[i];
		pos[i] = i;
	}
	sort(pos + 1, pos + M + 1, compare);
	
	for (int i = N; i >= 1; --i)
	{
		if (last[A[i]] != 0) next[i] = last[A[i]];
		else                 next[i] = N + 1;
		last[A[i]] = i;
		
		posA[i] = i;
	}
	sort(posA + 1, posA + N + 1, compareA);
	
	int posnow = 1;
	for (int i = 1; i <= M; ++i)
	{
		while (posnow <= N && next[posA[posnow]] > Right[pos[i]])
		{
			update(posA[posnow], A[posA[posnow]]);
			++posnow;
		}
		result[pos[i]] = query(Right[pos[i]]) - query(Left[pos[i]] - 1);
		if (result[pos[i]] < 0) result[pos[i]] += MOD;
	}
	
	for (int i = 1; i <= M; ++i)
		fout << result[i] << '\n';
	
	fin.close();
	fout.close();
}