#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 100005

int N, K, M;
vector<int> poz[MAXN];

vector< pair<int, int> > q;
int x[MAXN], o[MAXN], rez[MAXN];

int aib[MAXN];

int cmp( int a, int b ) { return q[a].second > q[b].second; }

#define MOD 666013

inline void set( int poz )
{
	for (int i = poz; i < MAXN; i += (i ^ (i - 1)) & i)
	{
		aib[i] += x[poz];
		if (aib[i] >= MOD)
			aib[i] -= MOD;
	}
}

inline int query( int poz )
{
	int rez = 0;
	for (; poz; poz -= (poz ^ (poz - 1)) & poz)
	{
		rez += aib[poz];
		if (rez >= MOD)
			rez -= MOD;
	}
	return rez;
}

int main()
{
	freopen("distincte.in", "rt", stdin);
	freopen("distincte.out", "wt", stdout);

	scanf("%d %d %d", &N, &K, &M);
	for (int i = 1; i <= N; i++)
		scanf("%d", x + i),
		poz[ x[i] ].push_back(i);

	for (int i = 0; i < M; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);

		q.push_back( make_pair(a, b) );
		o[i] = i;
	}

	sort( o, o + M, cmp );

	for (int i = 1; i <= K; i++)
		if (!poz[i].empty())
			set( poz[i].back() );

	for (int i = N, j = 0; i; i--)
	{
		for (; q[ o[j] ].second == i; j++)
			rez[ o[j] ] = (query( q[ o[j] ].second ) - query( q[ o[j] ].first - 1 ) + MOD) % MOD;
	
		poz[ x[i] ].pop_back();
		if (!poz[ x[i] ].empty())
			set( poz[ x[i] ].back() );
	}

	for (int i = 0; i < M; i++)
		printf("%d\n", rez[i]);

	return 0;
}