{$q-,r-,s-,d-,i-}
const maxn=100006;maxshl=17;modu=666013;
var t,tout:Text;
A,Y,Prev:Array[0..maxn]of longint;
V,Suma:Array[0..maxshl,0..maxn]of longint;
{O[lo..hi]-indecsi pentru punctele alea ordonate
unde[pula]-locul corespunzator la cautare binare
pizda masii nu merge preprocesare binara
}
k,xx,yy,return,n,m,i:longint;
Procedure BagaMare(adanc,lo,hi:longint);
var juma,i,j,lg,acum:longint;
begin
if (lo=hi)then begin V[adanc,lo]:=lo;suma[adanc,lo]:=A[lo];end else
begin
juma:=(lo+hi)div 2;acum:=0;
Bagamare(adanc+1,lo,juma);bagamare(adanc+1,juma+1,hi);
i:=lo;j:=juma+1;
for lg:=lo to hi do
if(j>hi)or(i<=juma)and(Y[V[adanc+1][i]]<Y[V[adanc+1][j]])then
begin
V[adanc][lg]:=v[adanc+1][i];
inc(acum,A[v[adanc+1][i]]);
if acum>=modu then dec(acum,modu);
Suma[adanc][lg]:=acum;inc(i);
end else
begin
V[adanc][lg]:=v[adanc+1][j];
inc(acum,A[v[adanc+1][j]]);
if acum>=modu then dec(acum,modu);
Suma[adanc][lg]:=acum;inc(j);
end;
end;
end;
procedure get(adanc,lo,hi,i,j,sus:longint);
var juma,stanga,dreapta,sol:longint;
begin
if(i<=lo)and(hi<=j)then
begin
{cautare binara ca sa ia muie intre lo..hi care termen
este cel mai mare si <=sus in functie de Y[V[adanc,termen]]}
sol:=0;stanga:=lo;dreapta:=hi;
while stanga<=dreapta do
begin
juma:=(stanga+dreapta)div 2;
if Y[V[adanc,juma]]<=sus then
begin if sol<juma then sol:=juma;stanga:=juma+1;
end else dreapta:=juma-1;
end;
if sol>0 then
begin
inc(return,Suma[adanc,sol]);
if return>=modu then dec(return,modu);
end;
end else
begin
juma:=(lo+hi)div 2;
if i<=juma then get(adanc+1,lo,juma,i,j,sus);
if juma<j then get(adanc+1,juma+1,hi,i,j,sus);
end;
end;
begin
assign(t,'distincte.in');reset(t);readln(T,n,k,m);
assign(tout,'distincte.out');rewrite(Tout);
for i:=1 to N do begin readln(t,A[i]);Y[i]:=Prev[A[i]];prev[A[i]]:=i;end;
BagaMare(0,1,N);{:) }
for i:=1 to m do
begin
readln(t,xx,yy);return:=0;
get(0,1,N,xx,yy,xx-1);
writeln(tout,return);
end;
close(T);close(Tout);
end.