#include<fstream>
#include<algorithm>

#define NMAX 100005
#define MOD 666013
#define mod(a) (a = (a >= MOD ? a - MOD : (a < 0 ? a + MOD : a)))

using namespace std;

ifstream f("distincte.in");
ofstream g("distincte.out");

struct Query {
	int ind , node1, node2 ;
}Q[NMAX];
int AIB[NMAX];

int N,M,v[NMAX],urm[NMAX],Sol[NMAX],K;

struct cmp {
	bool operator() (const Query &A , const Query &B ) const
	{
		if( A.node1 == B.node1 )
			return A.node2  > B.node2 ;
		return A.node1 > B.node1;
	
	}
};
inline int Lsb ( int x )
{
	return x&(-x);
}

inline void Update ( int val , int node )
{
	for(;node <= N ; node +=  Lsb(node) )
	{
		AIB[node] += val ;
		mod(AIB[node]);
	}
}
inline int QueryAib ( int node )
{
	int Answer = 0 ;
	for( ; node > 0 ; node -= Lsb(node) )
	{
		Answer += AIB[node];
		mod(Answer);
	}
	return Answer;
}

int main ( void )
{
	int i , j ;
	f>>N>>K>>M;
	for( i = 1 ; i <= N ; ++i )
		f>>v[i];
	for( i = 1 ; i <= M ; ++i )
		f>>Q[i].node1>>Q[i].node2,Q[i].ind = i ;
	//sortez intervale pt a putea lucra mai usor
	//in AIB
	sort( Q + 1 ,Q + M + 1 , cmp() );
	for ( i = 1 , j = N ; i <= M ; ++i )
	{
		for( ; j >= Q[i].node1 ; --j )
		{
			//adaug valoarea curenta 
			Update(v[j],j);
			//scot urmatorul pt a pastra unicitiatea elementului pe interval
			if( urm[v[j]] <= 0 )
             goto skip ;				
			Update(-v[j],urm[v[j]]);
			//marchez urmatorul 
			skip : urm[v[j]] = j ;
		}
		Sol[Q[i].ind] = QueryAib(Q[i].node2);
		mod(Sol[Q[i].ind]);
	}
	for( i = 1 ; i <= M ; ++i )
		g<<Sol[i]<<"\n";
	g<<(  Sol[M+1] < 1 ? 1 : 0 ) ;
	f.close();
	g.close();
	return 0;
}