const
  lim=100005;
  base=666013;
var
  v,a:array[1..lim] of longint;
  x,y,sum,i,j,n,m,k:longint;

begin
  assign(input,'distincte.in');
  reset(input);
  assign(output,'distincte.out');
  rewrite(output);
  readln(n,k,m);
  for i:=1 to n do
    readln(a[i]);
  for i:=1 to m do
  begin
    readln(x,y);
    sum:=0;
    for j:=x to y do
    begin
      inc(v[a[j]]);
      if v[a[j]]=1 then inc(sum,a[j]);
      if sum>=base then dec(sum,base);
    end;
    for j:=x to y do
      v[a[j]]:=0;
    writeln(sum);
  end;
  close(input);
  close(output);
end.