#include <iostream>
#include <fstream>
#include <algorithm>
#define nmx 100005
#define zeros(x) (x^(x-1))&x

using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");

int n,k,m,i,j,l,mod=666013;
int v[nmx],aib[nmx],pos[nmx],rez[nmx];
struct que
{	
	int a,b,id;
	bool operator<(const que &alt)const
	{	return b<alt.b;	}
} q[nmx];

void update(int x,int val)
{
	for(;x<=n;x+=zeros(x))	
	{
		aib[x]+=val;
		if(aib[x]>=mod)	aib[x]-=mod;
	}
}
int query(int x)
{
	int s=0;
	for(;x>0;x-=zeros(x))
	{
		s+=aib[x];
		if(s>=mod)	s-=mod;
	}
	return s;
}

int main() {
	
	fin>>n>>k>>m;
	for(i=1;i<=n;i++)
		fin>>v[i];
	for(i=1;i<=m;i++)
	{
		fin>>q[i].a>>q[i].b;
		q[i].id=i;
	}
	sort(q+1,q+m+1);
	
	j=1;
	for(i=1;i<=n;i++)
	{
		k=v[i];
		if(pos[k])	update(pos[k],-k);
		update(i,k);
		
		while(j<=m && q[j].b==i)
		{
			l=q[j].id;
			rez[l]=query(q[j].b)-query(q[j].a-1);
			if(rez[l]<0)	rez[l]+=mod;
			j++;
		}
		pos[k]=i;
	}
	
	for(i=1;i<=m;i++)
		fout<<rez[i]<<"\n";
}