var s,a,poz:array[0..100000] of int64;
    f,g:text;
    k,n,m,i,q,y,x,j:longint;
function cauta(x,st,dr:longint):longint;
 var mij:longint;
 begin
  if st>dr then
   cauta:=0
  else begin
   mij:=(st+dr) div 2;
   if a[mij]=x then
    cauta:=mij
   else
    if a[mij]<x then
     cauta:=cauta(x,mij+1,dr)
    else
     cauta:=cauta(x,st,mij-1);
  end;
 end;
begin
 assign(f,'distincte.in'); reset(f);
 assign(g,'distincte.out'); rewrite(g);
 read(f,n,k,m);
 s[0]:=0;
 for i:=1 to n do begin
  read(f,a[i]);
  s[i]:=s[i-1];
  q:=cauta(a[i],1,i-1);
  if q=0 then
   s[i]:=s[i]+a[i]
  else
   poz[i]:=q;
 end;
 for i:=1 to m do begin
  read(f,x,y);
  q:=(s[y]-s[x-1]) mod 666013;
  writeln(g,q);
 end;
 close(f); close(g);
end.