const ct=666013;
var f,g:text;
    c,s1,s2:array[1..100000] of longint;
    ap:array[1..100000] of byte;
    smax,saux,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);
fillchar(ap,sizeof(ap),0);
smax:=(qword(k)*qword((k+1))div 2) mod ct;
saux:=smax;
for i:=1 to n do
 begin
 if ap[c[i]]=0 then
  begin
  saux:=(saux-c[i])mod ct;
  if saux<0 then saux:=ct+saux;
  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])mod ct;
  if saux<0 then saux:=ct+saux;
  ap[c[i]]:=1;
  end;
 s2[i]:=saux;
 end;


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