#include <cstdio>
#include <string>
#include <cstdlib>
#define maxn 100005
#define mod 666013
int x[maxn];
char ax[200000*16];
int N, M, K;
bool viz[maxn];
int solve(int a, int b)
{
	
	register int i, j;
	register int sum=0;
	for(i=a; i<=b;i++)
		if(!viz[x[i]])
		{
			sum+=x[i];
			while(sum>mod) sum-=mod;
			viz[x[i]]=1;
		}
	for(i=a;i<=b;i++) viz[x[i]]=0;
	while(sum>mod) sum-=mod;
	return sum;
}

void citire()
{
	freopen("distincte.in", "r", stdin);
	scanf("%d %d %d\n", &N, &K, &M);
	fread(ax, sizeof(char), 200000*16, stdin);
	char *p;
	p=strtok(ax, " \n");
	x[1]=atoi(p);
	register int i;
	for(i=2;i<=N;i++)
	{
		p=strtok(0, " \n");
		x[i]=atoi(p);
	}
	register int a, b;
	for(i=1;i<=M;i++)
	{
		p=strtok(0, " ");
		a=atoi(p);
		p=strtok(0, " \n");
		b=atoi(p);
		printf("%d\n",solve(a, b));
	}
	
}

int main()
{
	freopen("distincte.out", "w", stdout);
	citire();
	return 0;
	
}