#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define ff first
#define ss second

const int NMAX=100001;
const int MOD=666013;

int N,M,K,x[NMAX],a[262150],ans[NMAX];
vector<int> Poz[NMAX];
pair< pair<int,int> , int > Q[NMAX];

void update(int n,int l,int r,int where,int what)
{
	if (l==r)
	{
		a[n]=what;
		return;
	}
	int m=(l+r)/2;
	if (where <= m) update(2*n,l,m,where,what);
	else update(2*n+1,m+1,r,where,what);
	
	a[n]=a[2*n]+a[2*n+1];
	if (a[n] >= MOD) a[n]-=MOD;
}

int query(int n,int l,int r,int st,int dr)
{
	if (l==st && dr==r) return a[n];
	int m=(l+r)/2;
	if (dr<=m) return query(2*n,l,m,st,dr);
	else
	if (st>m) return query(2*n+1,m+1,r,st,dr);
	else
	{
		int ret=query(2*n,l,m,st,m)+query(2*n+1,m+1,r,m+1,dr);
		if (ret >= MOD) ret-=MOD;
		return ret;
	}
}

int main()
{
	int i,q;
	ifstream fin("distincte.in");
	fin>>N>>K>>M;
	for (i=1;i<=N;++i)
	{
		fin>>x[i];
		Poz[x[i]].push_back(i);
	}
	for (i=1;i<=M;++i)
	{
		fin>>Q[i].ff.ff>>Q[i].ff.ss;
		Q[i].ss=i;
	}
	
	//printf("%lf\n",(double)sizeof(Poz)/1024);
	
	sort(Q+1,Q+M+1);
	
	for (i=1;i<=K;++i)
	{
		reverse(Poz[i].begin(),Poz[i].end());
	    if (!Poz[i].empty())
			update(1,1,N,Poz[i].back(),i);
	}
			
    for (q=1,i=1;q<=M;++q)
    {
		for (;i<Q[q].ff.ff;++i)
		{
			//update(1,1,N,i,0);
			Poz[x[i]].pop_back();
			if (!Poz[x[i]].empty())
			  update(1,1,N,Poz[x[i]].back(),x[i]);
		}
		ans[Q[q].ss]=query(1,1,N,Q[q].ff.ff,Q[q].ff.ss);
	}
	
	ofstream fout("distincte.out");
	for (q=1;q<=M;++q)
		fout<<ans[q]<<"\n";
	
	return 0;
}