#include <cstdio>
#include <cstring>


#define file_in "distincte.in"
#define file_out "distincte.out"

#define zeros(x) ((x^(x-1))&x)

#define Nmax 100100
#define Mod 666013

int n,m,k;
int v[Nmax];
int aib[Nmax];
int frecv[Nmax];
int a,b;

void add(int x, int val)
{
	int i;
	for (i=x;i<=n;i+=zeros(i))
		 aib[i]+=val;
}

int compute(int x)
{
	int i,ret=0;
	for (i=1;i<=k;++i)
		 frecv[i]=0;
	for (i=x;i>=1;i-=zeros(i))
	{	 //frecv[aib[i]]=1;
	//for (i=1;i<=k;++i)
		//printf("%d ", aib[i]);
	//printf("\n");
		// if (frecv[i]==1)
			ret+=aib[i];
			//printf("%d ", ret);
	}
	//printf("\n");
	return ret;	 
}

int main()
{
	int i,x;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d %d", &n,&k,&m);
    for (i=1;i<=n;++i)
    {
         scanf("%d", &v[i]);
         add(i,v[i]);
    }
	
	int nr;
	while(m--)
	{
		scanf("%d %d", &a,&b);
		x=compute(b)-compute(a-1);
		nr=0;
		for (i=1;i<=k;++i)
			 frecv[i]=0;
		for (i=a;i<=b;++i)
		      frecv[v[i]]++;
		for (i=1;i<=k;++i)
		//printf("%d ", frecv[i]);
		if (frecv[i]>1)
				nr+=i;
		printf("%d\n",(x-nr)%Mod);	 
			
		
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}