#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[NMAX],x[NMAX],ap[NMAX],n;
pair <int , int> p[NMAX];
qtype v[NMAX];
 
inline int LSB(int x)
{
	return x & (-x);
}

inline void update(int i, int val)
{
	for( ;i<=n;i=i+LSB(i))
		arb[i]=(arb[i]+val)%MOD;
}


inline int query(int i)
{
	int s;
	s=0;
	for( ;i>=1;i=i-LSB(i))
		s=(s+arb[i])%MOD;
	return s;
}

int main ()
{
	int 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++) 
			update(p[j].first,x[p[j].first]);
		ap[v[i].poz]=(query(v[i].dr)-query(v[i].st-1)+MOD)%MOD;
	}
	for(i=1;i<=m;i++)
		g<<ap[i]<<'\n';
	g.close();
	return 0;
}