{$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.