#include<stdio.h>
#include<algorithm>
using namespace std;
#define prim 666013
struct vect
{
	int st,dr,poz;
};
int n,k,m;
int v[100002],f[100002],sol[100002],csol[100002];
long long aib[100002];
vect v1[100002];

inline bool cmp(vect a, vect b)
{
	return a.dr<b.dr;
}

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

void update(int poz, int val)
{
	while(poz<=n)
	{
		aib[poz]+=val;
		poz+=lsb(poz);
	}
}

int query(int poz)
{
	int sol=0;
	while(poz)
	{
		sol=((long long)sol+aib[poz])%prim;
		poz-=lsb(poz);
	}
	return sol;
}

int main()
{
	freopen("distincte.in","r",stdin);
	freopen("distincte.out","w",stdout);
	scanf("%d%d%d",&n,&k,&m);
	int i,j;
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	for(i=1;i<=m;i++)
		scanf("%d%d",&v1[i].st,&v1[i].dr),v1[i].poz=i;
	sort(v1+1,v1+m+1,cmp);
	for(i=1;i<=m;i++)
	{
		for(j=v1[i-1].dr+1;j<=v1[i].dr;j++)
		{
			if(f[v[j]]==0)
			{
				f[v[j]]=j;
				update(j,v[j]);
			}
			else
			{
				update(f[v[j]],-v[j]);
				update(j,v[j]);
				f[v[j]]=j;
			}
		}
		sol[i]=query(v1[i].dr)-query(v1[i].st-1);
		if(sol[i]<0)
			sol[i]+=prim;
	}
	for(i=1;i<=m;i++)
		csol[v1[i].poz]=sol[i];
	for(i=1;i<=m;i++)
		printf("%d\n",csol[i]);
	return 0;
}