const ct=666013;
var f,g:text;
    c:array[1..100000] of longint;
    ap:array[1..100000] of byte;
    s1,v,t,n,m,i,j,k:longint;

begin
assign(f,'distincte.in'); reset(F);
readln(f,n,k,m);
for i:=1 to n do
 readln(f,c[i]);
assign(g,'distincte.out'); rewrite(g);

for t:=1 to m do
 begin
 readln(f,i,j);
 s1:=0;
 fillchar(ap,sizeof(Ap),0);
 for v:=i to j do
  if ap[c[v]]=0 then
   begin
   s1:=(s1+c[v])mod ct;
   ap[c[v]]:=1;
   end;
 writeln(g,s1);
 end;
close(F);
close(G);
end.