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

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);
fillchar(ap,sizeof(ap),0);
smax:=k*(k+1)div 2;
saux:=smax;
for i:=1 to n do
 begin
 if ap[c[i]]=0 then
  begin
  saux:=saux-c[i];
  ap[c[i]]:=1;
  end;
 s1[i]:=saux;
 end;
saux:=smax;
fillchar(ap,sizeof(ap),0);
for i:=n downto 1 do
 begin
 if ap[c[i]]=0 then
  begin
  saux:=saux-c[i];
  ap[c[i]]:=1;
  end;
 s2[i]:=saux;
 end;


for t:=1 to m do
 begin
 readln(f,i,j);
 writeln(g,(smax+s2[i]-s1[j]) mod ct);
 end;
close(F);
close(G);
end.