const max=1000;
var v,index:array[0..max] of longint;
interv:array[0..max] of record x,y,c:longint;end;
ui:array[0..max] of longint;
sum:array[0..max] of longint;
sminus,j,k,n,m,i,nint,x,y:longint;
procedure Quicksort(l, r: longint);
var
  i, j: longint;
    mij,help,mi:longint;
    begin
mij := v[(l+r) div 2];
mi:=index[(l+r) div 2];
i := l; j := r;
repeat
while (v[i]<mij)or((v[i]=mij)and(index[i]<mi)) do inc(i);
while (mij<v[j])or((v[j]=mij)and(index[j]>mi)) do dec(j);
if i <= j then begin
Help := v[i]; v[i] := v[j]; v[j] := Help;
Help := index[i]; index[i] := index[j]; index[j] := Help;
inc(i); dec(j);
end;
until i > j;
if l < j then Quicksort(l, j);
if i < r then Quicksort(i, r);
end;

procedure Quicksort2(l, r: longint);
var
  i, j: longint;
    mij,help,mi:longint;
    begin
mij := interv[(l+r) div 2].x;
mi:=interv[(l+r) div 2].y;
i := l; j := r;
repeat
while (interv[i].x<mij)or((interv[i].x=mij)and(interv[i].y<mi)) do inc(i);
while (mij<interv[j].x)or((interv[j].x=mij)and(interv[j].y>mi)) do dec(j);
if i <= j then begin
Help := interv[i].x; interv[i].x := interv[j].x; interv[j].x := Help;
Help := interv[i].y; interv[i].y := interv[j].y; interv[j].y := Help;
Help := interv[i].c; interv[i].c := interv[j].c; interv[j].c := Help;
inc(i); dec(j);
end;
until i > j;
if l < j then Quicksort(l, j);
if i < r then Quicksort(i, r);
end;


begin
assign(input,'distincte.in');
reset(input);
assign(output,'distincte.out');
rewrite(output);
readln(n,k,m);
for i:=1 to n do
begin
readln(v[i]);
sum[i]:=(sum[i-1]+v[i])mod 666013;
index[i]:=i;
end;
quicksort(1,n);
for i:=1 to n-1 do
begin
if (v[i]=v[i+1]) then
begin
inc(nint);
interv[nint].x:=index[i];
interv[nint].y:=index[i+1];
interv[nint].c:=v[i];
end
{else
ui[v[i+1]]:=i+1;}
end;
quicksort2(1,nint);
for i:=1 to nint-1 do
if interv[i].x<>interv[i+1].x then
ui[interv[i+1].x]:=i+1;
ui[interv[1].x]:=1;
for i:=n downto 1 do
if ui[i]=0 then
ui[i]:=ui[i+1];
for i:=1 to m do
begin
readln(x,y);
sminus:=0;
j:=ui[x];
repeat
if (x<=interv[j].x)and(interv[j].y<=y) then
sminus:=(sminus+interv[j].c)mod 666013
else
j:=ui[interv[j].x+1]-1;
inc(j);
until (interv[j].x>y)or(j=1);
if sum[y]-sum[x-1]-sminus<0 then
writeln(sum[y]-sum[x-1]-sminus+666013)
else
writeln((sum[y]-sum[x-1]-sminus) mod 666013)
end;
close(output);
end.