//uses timer;
const LMax=511;
type sir=array[0..LMax] of longint;
var a,nr,gr,poz:array[0..103000] of longint;
st,fn,total:array[0..103000 div LMax] of longint;
buc,sum:array[0..103000 div LMax] of sir;
i,j,m,n,lung,p,u:longint;

procedure sort(k,l,r: longint);
var i,j,x,y: longint;
begin
i:=l; j:=r;
x:=buc[k][(l+r) div 2];
repeat
 while buc[k][i]<x do inc(i);
 while x<buc[k][j] do dec(j);
 if (i<=j) then
       begin
       y:=buc[k][i]; buc[k][i]:=buc[k][j]; buc[k][j]:=y;
       y:=sum[k][i]; sum[k][i]:=sum[k][j]; sum[k][j]:=y;
       inc(i); dec(j);
       end;
until i>j;
if l<j then sort(k,l,j);
if i<r then sort(k,i,r);
end;

function cbin(var a:sir; k:longint):longint; inline;
var poz:longint=0;
begin
if (a[poz+ 256]<=k) then inc(poz, 256);
if (a[poz+ 128]<=k) then inc(poz, 128);
if (a[poz+  64]<=k) then inc(poz,  64);
if (a[poz+  32]<=k) then inc(poz,  32);
if (a[poz+  16]<=k) then inc(poz,  16);
if (a[poz+   8]<=k) then inc(poz,   8);
if (a[poz+   4]<=k) then inc(poz,   4);
if (a[poz+   2]<=k) then inc(poz,   2);
if (a[poz+   1]<=k) then inc(poz,   1);
cbin:=poz;
end;

procedure build; inline;
var i,j,k:longint;
begin
lung:=round(sqrt(n*ln(n)));
if lung>LMax then lung:=LMax;
for i:=n+1 to n+lung do nr[i]:=2*n;
while (n mod lung<>0) do inc(n);
for i:=1 to n+1 do gr[i]:=(i-1) div lung+1;
for i:=1 to n div lung do
 begin
 st[i]:=(i-1)*lung+1; fn[i]:=i*lung;
 for j:=st[i] to fn[i] do buc[i, j-st[i]+1]:=nr[j];
 for j:=st[i] to fn[i] do sum[i, j-st[i]+1]:=a[j];
 for j:=lung+1 to LMax do buc[i,j]:=2*n;
 sort(i, 1, lung);
 for j:=2 to lung do
  inc(sum[i][j], sum[i][j-1]);
 total[i]:=sum[i][lung];
 end;
st[n div lung+1]:=n+1;
end;

procedure ask(x1,x2:longint); inline;
var i,j,k:longint;
rez:int64;
begin
rez:=0;
for k:=gr[x1-1]+1 to gr[x2+1]-1 do
 begin
 rez:=rez+total[k]-sum[k, cbin(buc[k], x2)];
 end;
for i:=x1 to fn[gr[x1-1]] do
 if (x2<nr[i]) then inc(rez, a[i]);
for i:=st[gr[x2+1]] to x2 do
 if (x2<nr[i]) then inc(rez, a[i]);
writeln(rez mod 666013);
end;

begin
//start;
assign(input,'distincte.in'); reset(input);
assign(output,'distincte.out'); rewrite(output);
readln(n, i, m);
for i:=1 to n do
 readln(a[i]);
for i:=1 to n do
 poz[i]:=n+1;
for i:=n downto 1 do
 begin
 nr[i]:=poz[a[i]];
 poz[a[i]]:=i;
 end;
build;
for i:=1 to m do
 begin
 readln(p, u);
 ask(p, u);
 end;
//scurs;
close(input); close(output);
end.