#include <fstream>
#include <algorithm>
#define MOD 666013
#define NMAx 100100
using namespace std;

int N,K,M,AIB[NMAx],V[NMAx],Sol[NMAx],Last[NMAx];
struct query{int i,A,B;}Query[NMAx];

inline bool cmp(query X,query Y) {
	return X.A>Y.A;
}
inline void Modul(int & Val) {
	
	if(Val>=MOD)
		Val-=MOD;
	else
	if(Val<0)
		Val+=MOD;
	
}
void AIBUpdate(int Nod,int Val) {
	
	if(!Nod) return;
	
	while(Nod<=N) {
		AIB[Nod]+=Val;
		Modul(AIB[Nod]);
		Nod+=(Nod&-Nod);
		}
	
}
int AIBQuery(int Nod) {
	
	int Sum=0;
	
	while(Nod>0) {
		Sum+=AIB[Nod];
		Modul(Sum);
		Nod-=(Nod&-Nod);
		}
	
	return Sum;
	
}
void Solve() {
	
	int i,j;
	
	sort(Query+1,Query+M+1,cmp);
	
	for(i=1,j=N;i<=M;i++) {
		
		for(;j>=Query[i].A;j--) {
			AIBUpdate(j,V[j]);
			AIBUpdate(Last[V[j]],-V[j]);
			Last[V[j]]=j;
			}
		
		Sol[Query[i].i]=AIBQuery(Query[i].B);
		
		}
	
}
void Citire() {
	
	ifstream in("distincte.in");
	in>>N>>K>>M;
	
	for(int i=1;i<=N;in>>V[i++]);
	
	for(int i=1;i<=M;i++) {
		in>>Query[i].A>>Query[i].B;
		Query[i].i=i;
		}
	
	in.close();
	
}
void Afis() {
	
	ofstream out("distincte.out");
	for(int i=1;i<=M;out<<Sol[i++]<<'\n');
	out.close();
	
}
int main() {
	
	Citire();
	Solve();
	Afis();
	
	return 0;
	
}