//distincte
#include <stdio.h>
#define INPUT "distincte.in"
#define OUTPUT "distincte.out"
#define CONST 666013
#define MAX 100001
#define LOG 17
int N, K, M;
int urm[MAX], v[MAX], prec[MAX];
int c[LOG][LOG];
void aduna (int val, int x, int y)
{
	int i, j;
	for(i = x; i <= LOG; i += i&(i^(i-1)))
		for(j = y; j <= LOG; j += j&(j^(j-1)))
			if(i <= LOG && j <= LOG)
			c[i][j] = (c[i][j] + val) % CONST;
}
int inter(int st, int dr)
{
	int i, j;
	int sum = 0;
	for(i = st; i > 0; i -= i&(i^(i-1)))
		for(j = dr; j > 0; j -= j&(j^(j-1)))
			sum = (sum + c[i][j]) % CONST;
	return sum;
}
int query(int st, int dr)
{
	return (inter(dr, N+1) - inter(dr, dr) - inter(st-1, N+1) + inter(st-1, dr)) % CONST;
}
int main()
{
	freopen(INPUT, "r", stdin);
	scanf("%d %d %d", &N, &K, &M);
	int i;
	for(i = 1; i <= N; ++i)
		scanf("%d", &v[i]);
	for(i = 1; i <= N; ++i)
		urm[prec[v[i]]] = i,
		prec[v[i]] = i;
		
	for(i = 1; i <= N; ++i)
		if(!urm[i]) urm[i] = N+1;
	for(i = 1; i <= N; ++i)
		aduna(v[i], i, urm[i]);
	int j;
/*	for(i = 1; i <= N; ++i)
	{
		for(j = 1; j <= N+1; j++)
			printf("%d ",c[i][j]);
		printf("\n");
	}*/
	freopen(OUTPUT, "w", stdout);
	int st, dr;
	for(i = 1; i <= M; ++i)
	{
		scanf("%d %d", &st, &dr);
		printf("%d\n", query(st, dr)) ;
	}
	return 0;
}