const maxn=100006;modu=666013;
var t:Text;
    Prev,A,Y,O,O2,XX,YY,aib,Count,sol,Op:Array[0..maxn]of longint;
    j,n,m,i:longint;
    Procedure RadixSort(N:longint;var A,B,BY:array of longint);
    var i:longint;
    begin
       fillchar(count,sizeof(count),0);
       for i:=1 to N do inc(Count[by[i]]);
       for i:=1 to maxn do inc(count[i],count[i-1]);
       for i:=N downto 1 do
       begin A[count[by[b[i]]]]:=b[i];dec(count[by[b[i]]]);end;
    end;
    Procedure Add(cine,cat:longint);
    var x:longint;
    begin
       x:=cine;
       while x<=N do
       begin
          inc(aib[x],cat);if aib[x]>=modu then dec(aib[x],modu);
          x:=x +x and (x xor (X-1));
       end;
    end;
    function get(cine:longint):longint;
    var x,return:longint;
    begin
       x:=cine;return:=0;
       while x>0 do
       begin
          inc(return,Aib[x]);if return>=modu then dec(return,modu);
          x:=x- x and (X xor (x-1));
       end;get:=return;
    end;
begin
   assign(t,'distincte.in');reset(t);readln(t,n,m,m);
   for i:=1 to N do readln(t,A[i]);
   for i:=1 to M do readln(T,xx[i],yy[i]);close(T);
   for i:=1 to N do begin Y[i]:=Prev[A[i]];Prev[a[i]]:=i;end;
   for i:=1 to M do O2[i]:=i;radixSort(M,Op,O2,XX);
   for i:=1 to N do O2[i]:=i;RadixSort(N,O,O2,Y);j:=1;
   for i:=1 to M do
   begin
      while (j<=N)and(Y[O[j]]<XX[Op[i]])do begin add(O[j],A[O[j]]);inc(j);end;
      Sol[Op[i]]:=get(YY[Op[i]])-get(XX[Op[i]]-1)+modu;
      if sol[op[i]]>=modu then dec(sol[op[i]],modu);
   end;
   assign(t,'distincte.out');rewrite(t);
   for i:=1 to M do writeln(T,Sol[i]);close(t);
end.