#include <stdio.h>
#include <stdlib.h>
#define N 1<<17
#define NR 666013
int n,k,m,v[N],ant[N],aib[N],ord[N],rsp[N];
struct query
{
	int a,b;
};
query nr[N];
int lsb(int x)
{
	return x & -x;
}
void update(int poz,int val)
{
	int i;
	if (!poz)
		return;
	for (i=poz; i<=n; i+=lsb(i))
	{
		aib[i]+=val;
		if (aib[i]<0)
			aib[i]+=NR;
		if (aib[i]>=NR)
			aib[i]%=NR;
	}
}
int sum(int poz)
{
	int i,s=0;
	for (i=poz; i>=1; i-=lsb(i))
	{
		s+=aib[i];
		if (s>=NR)
			s%=NR;
	}
	return s;
}
int compar(const void *p,const void *q)
{
	int x=*(int*)p;
	int y=*(int*)q;
	if (nr[x].b<nr[y].b)
		return -1;
	if (nr[x].b>nr[y].b)
		return 1;
	return 0;
}
int main()
{
	freopen("distincte.in","r",stdin);
	freopen("distincte.out","w",stdout);
	scanf("%d%d%d",&n,&k,&m);
	int i,start=0;
	for (i=1; i<=n; i++)
		scanf("%d",&v[i]);
	for (i=1; i<=m; i++)
	{
		scanf("%d%d",&nr[i].a,&nr[i].b);
		ord[i]=i;
	}
	qsort(ord+1,m,sizeof(ord[0]),compar);
	for (i=1; i<=n; i++)
	{
		update(i,v[i]);
		update(ant[v[i]],-v[i]);
		while (nr[ord[start+1]].b==i)
		{
			start++;
			rsp[ord[start]]=sum(nr[ord[start]].b)-sum(nr[ord[start]].a-1);
			if (rsp[ord[start]]<0)
				rsp[ord[start]]+=NR;
		}
		ant[v[i]]=i;
	}
	for (i=1; i<=m; i++)
		printf("%d\n",rsp[i]);
	return 0;
}