#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

#define NMAX 100010
#define MOD 666013
#define ff first
#define ss second
#define RED(x) if (x >= MOD) x -= MOD; if (x < 0) x += MOD;

int N, M, K;

int a[NMAX];

int poz[NMAX];

int jeg[NMAX];

int nap[NMAX];

int aib[NMAX];

pair <pair<int, int>, int> inter[NMAX];

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

char ap[NMAX];

int rez[NMAX];

int query(int x)
{
	int rez = 0;

	while (x) {
		rez += aib[x]; RED(rez);
		x -= lsb(x);
	}

return rez;
}

void update(int x, int sum)
{
	while (x <= N) {
		aib[x] += sum; RED(aib[x]);
		x += lsb(x);
	}
}

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

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

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

		if (!ap[ a[i] ]) update(i, a[i]);
		ap[a[i]] = 1;

		nap[ a[i] ] ++;
	}

	for (i = 1; i <= N; i++) jeg[i] = nap[i] + jeg[i-1];

	memset(nap, 0, sizeof(nap));

	for (i = 1; i <= N; i++) {
		nap[ a[i] ] ++;
		poz[ jeg[a[i] - 1] + nap[a[i]] ] = i;
	}

	for (i = 1; i <= N; i++) nap[i] = 1;

	for (i = 1; i <= M; i++) {
		scanf("%d %d", &inter[i].ff.ff, &inter[i].ff.ss);
		inter[i].ss = i;
	}

	sort(inter + 1, inter + M + 1);

	int ant = 1, j;

	for (i = 1; i <= M; i++) {
		for (j = ant; j < inter[i].ff.ff; j++) { 
			update(j, -a[j]);
			nap[a[j]]++;
			update(poz[ jeg[a[j]-1] + nap[a[j]] ], a[j]);
		}

		rez[ inter[i].ss ] = query( inter[i].ff.ss ) - query( inter[i].ff.ff - 1 );
		RED( rez[ inter[i].ss ] );
		ant = inter[i].ff.ff;
	}

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

fclose(stdin);
fclose(stdout);
return 0;
}