#include<fstream>
#include<cmath>
#include<algorithm>
#define MOD 666013
using namespace std;
int n,K,m,v[100100],pred[100100];
struct Intrebare{int st,dr,ind;};
Intrebare q[100100];
int aib[100100],bit[100100];
int sol[100100];

void Citire()
{
	int i;
	ifstream fin("distincte.in");
	fin>>n>>K>>m;
	for(i=1;i<=n;i++)
		fin>>v[i];
	for(i=1;i<=m;i++)
	{
		fin>>q[i].st>>q[i].dr;
		q[i].ind=i;
	}
	fin.close();
}

inline void Precalculare_Biti_Terminali()
{
	int i;
	for(i=1;i<=n;i++)
		bit[i]=(i & (-i));
}

inline bool Sortare(Intrebare A,Intrebare B)
{
	if(A.dr==B.dr)
		return A.st<B.st;
	return A.dr<B.dr;
}

inline void Update(int poz,int val)
{
	if(poz==0)
		return;
	while(poz<=n)
	{
		aib[poz]+=val;
		aib[poz]%=MOD;
		if(aib[poz]<0)
			aib[poz]+=MOD;
		poz+=bit[poz];
	}
}

inline int Suma(int poz)
{
	int sum=0;
	while(poz>0)
	{
		sum+=aib[poz];
		sum%=MOD;
		poz-=bit[poz];
	}
	return sum;
}

void Rezolvare()
{
	int i,poz=0;
	sort(q+1,q+m+1,Sortare);
	Precalculare_Biti_Terminali();
	for(i=1;i<=m;i++)
	{
		while(poz<q[i].dr)
		{
			poz++;
			Update(pred[v[poz]],-v[poz]);
			Update(poz,v[poz]);
			pred[v[poz]]=poz;
		}
		sol[q[i].ind]=Suma(q[i].dr)-Suma(q[i].st-1);
		if(sol[q[i].ind]<0)
			sol[q[i].ind]+=MOD;
	}
}

void Afisare()
{
	int i;
	ofstream fout("distincte.out");
	for(i=1;i<=m;i++)
		fout<<sol[i]<<"\n";
	fout.close();
}

int main()
{
	Citire();
	Rezolvare();
	Afisare();
	return 0;
}