{$q-,r-,s-,d-,i-}
const maxn=100006;maxshl=17;modu=666013;zero=ord('0');
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
     }
    adanc,sus,lg,j,k,xx,yy,return,n,m,i:longint;s:string;
   Procedure BagaMare(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;
         inc(adanc);
         Bagamare(lo,juma);bagamare(juma+1,hi);
         dec(adanc);
         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(lo,hi,i,j: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;inc(adanc);
         if i<=juma then get(lo,juma,i,j);
         if juma<j then get(juma+1,hi,i,j);
         dec(adanc);
      end;
   end;
{var t1:longint;t2:longint absolute $0:$046c;}
begin
{   t1:=t2;                     }
   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,S);j:=1;lg:=length(s);
      while j<=lg do begin a[i]:=A[i]*10+ord(s[j])-zero;inc(j);end;
      Y[i]:=Prev[A[i]];prev[A[i]]:=i;
   end;
   BagaMare(1,N);
   for i:=1 to m do
   begin
      readln(t,S);lg:=length(s);j:=1;xx:=0;yy:=0;return:=0;
      while S[j]<>' 'do begin xx:=xx*10+ord(S[j])-zero;inc(j);end;inc(j);
      while j<=lg do begin yy:=yy*10+ord(S[j])-zero;inc(j);end;
      sus:=xx-1;get(1,N,xx,yy);
      writeln(tout,return);
   end;
   close(T);close(Tout);
{   writeln((t2-t1)/18.2:0:6);}
end.