#include<cstdio>
#include<algorithm>
#define MX 100005
#define MOD 666013

static int t[MX];
static int p[100005];
static int v[100005];

static struct query
{
	int x,y,i,r;

	query()
		{
			x=y=i=r=0;
		}

	query (int xx,int yy,int ii)
		{
			x=xx;
			y=yy;
			i=ii;
			r=0;
		}

	bool operator<(const query& q)const
		{
			if(y<q.y)
				return 1;
			if(y>q.y)
				return 0;
			return x<q.x;
		}
} q[100005];

bool comp (const query& a,const query& b)
{
	return a.i<b.i;
}

void u (int i,int v)
{
	while(i<MX)
		t[i]=(t[i]+v)%MOD,i+=(i&-i);
}

int g (int i)
{
	int s=0;
	while(i)
		s=(s+t[i])%MOD,i-=(i&-i);
	return s;
}

int main(void)
{
	freopen ("distincte.in","r",stdin);
#ifdef INFOARENA
	freopen ("distincte.out","w",stdout);
#endif

	int n,m;
	scanf ("%d%*d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf ("%d",v+i);

	for(int i=0;i<m;i++){
		int x,y;
		scanf ("%d%d",&x,&y);
		q[i]=query (x,y,i);
	}

	std::sort (q,q+m);

	int end=1;
	for(int i=0;i<m;i++){
		for(;end<=q[i].y;end++){
			if(p[v[end]])
				u (p[v[end]],-v[end]);
			p[v[end]]=end;
			u (end,v[end]);
		}

		int ret=g (q[i].y) - g (q[i].x-1);
		q[i].r=(ret+MOD)%MOD;
	}

	std::sort (q,q+m,comp);

	for(int i=0;i<m;i++)
		printf ("%d\n",q[i].r);

	return 0;
}