const maxn = 100001;
      modul = 666013;

var f,fi:text;
    n,m,k,i,j,s,x,y:longint;
    a:array[1..maxn]of longint;
    fol:array[1..maxn]of boolean;

procedure readdata;
begin
   assign(f,'distincte.in');
   reset(f);
   assign(fi,'distincte.out');
   rewrite(fi);
   readln(f,n,k,m);
   for i:=1 to n do
   begin
      readln(f,a[i]);
   end;
   for i:=1 to m do
   begin
      readln(f,x,y);
      fillchar(fol,sizeof(fol),false);
      s:=0;
      for j:=x to y do
      begin
         if fol[a[j]]=false then s:=(s+a[j]) mod modul;
         fol[a[j]]:=true;
      end;
      writeln(fi,s);
   end;
   close(f);
   close(fi);
end;

begin
   readdata;
end.