#include<stdio.h>
#include<algorithm>

#define maxn 100005
#define mod 666013

using namespace std;

FILE*f=fopen("distincte.in","r");
FILE*g=fopen("distincte.out","w");

int n,k,q;
int v[maxn],r[maxn],last[maxn],aib[maxn];

struct pct{
	pct(int x = 0,int y = 0,int val = 0):x(x),y(y),val(val){}
	int x,y;
	int val;
}P[maxn];

struct query{
	int x,y;
	int ind;
}Q[maxn];

struct cmp1{
	inline bool operator () ( const pct &a , const pct &b ){
		if ( a.y != b.y )
			return a.y < b.y;
		return a.x < b.x;
	}
};

struct cmp2{
	inline bool operator () ( const query &a , const query &b ){
		if ( a.y != b.y )
			return a.y < b.y;
		return a.x < b.x;
	}
};

inline int lsb ( int x ){
	return x & (-x);
}

inline void update_aib ( int poz , int val ){
	
	while ( poz <= n ){
		aib[poz] += val; if ( aib[poz] >= mod )	aib[poz] -= mod;
		poz += lsb(poz);
	}
}

inline int query_aib ( int poz ){
	int s = 0;
	
	while ( poz > 0 ){
		s += aib[poz]; if ( s >= mod )	s -= mod;
		poz -= lsb(poz);
	}
	
	return s;
}

int main () {
	
	fscanf(f,"%d %d %d",&n,&k,&q);
	
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d",&v[i]);
	}
	
	int k = 0;
	for ( int i = n ; i >= 1 ; --i ){
		if ( !last[v[i]] ){
			P[++k] = pct(i,n+1,v[i]);
		}
		else{
			P[++k] = pct(i,last[v[i]],v[i]);
		}
		last[v[i]] = i;
	}
	
	for ( int i = 1 ; i <= q ; ++i ){
		fscanf(f,"%d %d",&Q[i].x,&Q[i].y);
		Q[i].ind = i;
	}
	
	sort(P+1,P+n+1,cmp1());
	sort(Q+1,Q+q+1,cmp2());
	
	int p = n;
	for ( int i = q ; i >= 1 ; --i ){
		while ( P[p].y > Q[i].y && p > 0 ){
			update_aib(P[p].x,P[p].val);
			--p;
		}
		r[Q[i].ind] = query_aib(Q[i].y)-query_aib(Q[i].x-1);
		if ( r[Q[i].ind] < 0 )	r[Q[i].ind] += mod;
	}
	
	for ( int i = 1 ; i <= q ; ++i ){
		fprintf(g,"%d\n",r[i]);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}