program distincte;
type vector=array[1..10001] of word;
tip1=record
        l:longint;
        v:vector;
end;
var f,g:text;
        v:array[1..100001] of tip1;
        n,m,k:longint;



procedure iofile;
var i,x:longint;
begin
        assign(f,'distincte.in');
        reset(f);
        assign(g,'distincte.out');
        rewrite(g);
        readln(f,n,k,m);
        for i:=1 to n do
            begin
                readln(f,x);
                inc(v[x].l);
                v[x].v[v[x].l]:=i;
            end;
end;




function cbin(var v:vector;p,u:longint;a,b:longint):byte;
var m:longint;
begin
        if p>u then cbin:=0 else
                begin
                        m:=(p+u) div 2;
                        if (v[m]>=a)and(v[m]<=b) then
                                cbin:=1 else
                                if v[m]<a then cbin:=cbin(v,m+1,u,a,b) else
                                cbin:=cbin(v,p,m-1,a,b);
                end;
end;



procedure query;
var s:longint;
        x,y,i:longint;
begin
        s:=0;
        readln(f,x,y);
        for i:=1 to k do
                if v[i].l>0 then
                        if cbin(v[i].v,1,v[i].l,x,y)=1 then
                                s:=(s+i) mod 666013;
        writeln(g,s);
end;


procedure prel;
var i:longint;
begin
        for i:=1 to m do
                query;
        close(f);
        close(g);
end;



begin
        iofile;
        prel;
end.