//infoarena distincte
const nmax= 100000;
var sir:array[1..nmax] of longint;
    uz: array[1..100000] of boolean;
    n,m,k:longint;

function query(x,y:longint):longint;
var rez:longint;
   i:longint;
begin
rez:=0;
for i:=x to y do
        if not uz[sir[i]] then
                begin
                reZ:=(rez+sir[i]) mod 666013;
                uz[sir[i]]:=true;
                end;
query:=rez;
{for i:=x to y do
        uz[sir[i]]:=false;}
fillchar(uz,sizeof(uz),false);
end;

procedure citire;
var i,x,y: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(sir[i]);
for i:=1 to m do
        begin
        readln(x,y);
        writeln(query(x,y));
        end;
close(input); close(output);
end;


begin
citire;
end.