#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX_N 100002
#define Mod 666013
#define DIM 8192
char vec[DIM];
int pz;
struct punct { int x,y,i,v; };
int first[MAX_N];
long long AIB[MAX_N];
int N,M,K,P;
punct A[2 * MAX_N];
long long sol[MAX_N];
void cit(int &x)   
 {   
  x=0;   
  while(vec[pz]<'0' || vec[pz]>'9')   
  
    if(++pz==DIM) fread(vec,1,DIM,stdin),pz=0;   
  
    while(vec[pz]>='0' && vec[pz]<='9')   
    {   
        x=x*10+vec[pz]-'0';   
        if(++pz==DIM)fread(vec, 1, DIM, stdin),pz=0;   
    }   
 }  
inline void update(int y, long long v)
{
	for(;y<=N;y+=(y & -y)) 
		AIB[y] += v;
}
inline long long query(int y)
{
	long long s = 0;
	for(;y;y-=(y & -y)) s = s + AIB[y];
	return s;
}
struct cmp 
{    
	bool operator()(const punct &a, const punct &b)const
	{       
		if(a.y == b.y)
		{
			if(a.i < b.i) return 0;
			return 1;
		}
		
		if(a.y < b.y) return 0;
		return 1;       
	} 
}; 
int main()
{
	freopen("distincte.in","r",stdin);
	freopen("distincte.out","w",stdout);
	cit(N), cit(K), cit(M);
	int i,x,y;
	for(i=1;i<=N;++i)
	{
		cit(x);
		if(first[x]) { A[++P].x = first[x]; A[P].y = i; A[P].i = 0; A[P].v = x; }
		first[x] = i;
	}
	for(i=1; i <= K; ++i) if(first[i]) { A[++P].x = first[i], A[P].v = i, A[P].y = N+1; A[P].i = 0;}
	for(i=1;i<=M;++i)
	{
		cit(x), cit(y);
		A[++P].x = x; A[P].y = y;
		A[P].i = i;
	}
	sort(A+1,A+N+M+1,cmp());
	for(i=1;i<=M+N;++i)
	{
		if(A[i].i == 0) update(A[i].x, (long long)A[i].v);
		else sol[A[i].i] = query(A[i].y) - query(A[i].x - 1);
	}
	for(i=1;i<=M;++i) printf("%lld\n",sol[i]%Mod);
	return 0;
}