#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define nmax 100111
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define f first
#define s second
#define MOD 666013

int n,m,k,A[nmax],s[nmax],last[nmax],sol[nmax],perm[nmax];
pair <int,int> P[nmax];

bool cmp(const int i,const int j)
{
	return P[i].f<P[j].f||(P[i].f==P[j].f&&i<j);
}

void Add(int i,int y)
{
	if(!i)
		return ;
	for(;i<=n;i=(i|(i-1))+1)
	{
		s[i]+=y;
		while(s[i]>=MOD)
			s[i]-=MOD;
		while(s[i]<0)
			s[i]+=MOD;
	}
}

int query(int i)
{
	int aux=0;
	for(;i;i&=i-1)
	{
		aux+=s[i];
		if(aux>=MOD)
			aux-=MOD;
	}
	return aux;
}

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

	scanf("%d %d %d",&n,&k,&m);
	FOR(i,1,n+1)
		scanf("%d",&A[i]);
	FOR(j,0,m)
		scanf("%d %d",&P[j].s,&P[j].f),	perm[j]=j;
	sort(perm,perm+m,cmp);
	j=0;
	FOR(i,1,n+1)
	{
		Add(i,A[i]);
		Add(last[A[i]],-A[i]);
		last[A[i]]=i;
		for(;j<m&&P[perm[j]].f==i;++j)
		{
			sol[perm[j]]=query(i)-query(P[perm[j]].s-1);
			if(sol[perm[j]]<0)
				sol[perm[j]]+=MOD;				
		}
	}
	FOR(i,0,m)
		printf("%d\n",sol[i]);
	return 0;
}