#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define nmax 100010
#define MOD 666013

int n,m,v[nmax],a[nmax],b[nmax],c[nmax],i,j,k,nr[nmax];

int main()
{
	freopen("distincte.in","r",stdin);
	freopen("distincte.out","w",stdout);

	scanf("%d%d%d",&n,&k,&m);
	for (i=1;i<=n;i++)
		scanf("%d",v+i);
	for (i=0;i<m;i++)
		scanf("%d%d",a+i,b+i);
	for (j=1;j<=k;j++)
	{
		memset(nr,0,sizeof(nr));
		for (i=1;i<=n;i++)
			nr[i]=((v[i]==j)?(nr[i-1]+1):nr[i-1]);
		for (i=0;i<m;i++)
			if (nr[b[i]]-nr[a[i]]>0)
				c[i]=(c[i]+j)%MOD;
	}
	for (i=0;i<m;i++)
		printf("%d\n",c[i]);

	return 0;
}