#include <stdio.h>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 100002
#define pb push_back
#define sz size()
#define mp make_pair
#define ff first
#define ss second
#define modulo 666013

int lst[NMAX];
int ARB[NMAX];
int A[NMAX];
int ans[NMAX];
vector< pair< pair<int, int>, int> > V;
int N, M, K;

void update(int val, int poz)
{
	int i;

	for (i = poz; i <= N; i += (i^(i-1)))
		ARB[i] = (ARB[i] + val) % modulo;
}

int query(int poz)
{
	int i, ret = 0;

	for (i = poz; i > 0 ; i -= (i^(i-1)) )
			ret = (ret + ARB[i]) % modulo;
	return ret;
}

int main()
{
	freopen("distincte.in","r",stdin);
	freopen("distincte.out","w",stdout);

	int i, j, x, y, mx=0;

	scanf("%d %d %d", &N, &K, &M);

	for (i = 1; i <= N; i++)
		scanf("%d ", &A[i]);

	for (i = 1; i <= M; i++)
	{
		scanf("%d %d", &x, &y);
		V.pb( mp(mp(y, x), i) );
	}

	sort(V.begin(), V.end());

	for (i = 0; i < M; i++)
	{
		x = V[i].ff.ss; y = V[i].ff.ff;
	
		for (j = mx + 1; j <= y; j++)
			{
				if (lst[ A[j] ]) update(-A[j], lst[ A[j] ]);
				lst[ A[j] ] = j;
				update(A[j], j);
			}
		mx = y;
		ans[ V[i].ss ] = query(y) - query(x-1);
	}

	for (i = 1; i <= M; i++)
		printf("%d\n", ans[i]);
	return 0;
}