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

#define NMAX 100001
#define MOD 666013
#define urm second

struct qtype {
	int st,dr,poz;
};

struct cmp {
	bool operator () (const qtype &a, const qtype &b) {
		if(a.dr==b.dr)
			return a.st<b.st;
		return a.dr>b.dr;
	}
};

struct cmp2 {
	bool operator () (const pair <int , int> &a, const pair <int , int> &b) {
		return a.urm>b.urm;
	}
};

int arb[4*NMAX+1],x[NMAX],ap[NMAX],poz,val,a,b;
pair <int , int> p[NMAX];
qtype v[NMAX];

inline void update(int nod, int st, int dr)
{
	int mij;
	if(st==dr) {
		arb[nod]=val;
		return;
	}
	mij=(st+dr)/2;
	if(poz<=mij)
		update(nod*2,st,mij);
	else update(nod*2+1,mij+1,dr);
	arb[nod]=arb[2*nod]+arb[2*nod+1];
	if(arb[nod]>=MOD)
		arb[nod]=arb[nod]-MOD;
}

inline void query(int nod, int st, int dr)
{
	int mij;
	if(a<=st && dr<=b) {
		val=val+arb[nod];
		if(val>=MOD)
			val=val-MOD;
		return ;
	}
	mij=(st+dr)/2;
	if(a<=mij)
		query(nod*2,st,mij);
	if(mij<b)
		query(nod*2+1,mij+1,dr);
}

int main ()
{
	int n,m,i,j,k;
	ifstream f("distincte.in");
	ofstream g("distincte.out");
	f>>n>>k>>m;
	for(i=1;i<=n;i++) {
		f>>x[i];
		p[i].urm=n+1;
		p[i].first=i;
	}
	for(i=1;i<=m;i++) {
		f>>v[i].st>>v[i].dr;
		v[i].poz=i;
	}
	f.close();
	sort(v+1,v+m+1,cmp());
	ap[x[n]]=n;
	for(i=n-1;i>=1;i--) {
		if(ap[x[i]])
			p[i].urm=ap[x[i]];
		ap[x[i]]=i;
	}
	sort(p+1,p+n+1,cmp2());
	for(i=1,j=1;i<=m;i++) {
		for( ;j<=n && p[j].urm>=(v[i].dr+1);j++) {
			val=x[p[j].first];
			poz=p[j].first;
			update(1,1,n);
		}
		val=0;
		a=v[i].st;
		b=v[i].dr;
		query(1,1,n);
		ap[v[i].poz]=val;
	}
	for(i=1;i<=m;i++)
		g<<ap[i]<<'\n';
	g.close();
	return 0;
}