//infoarena distincte

const fin = 'distincte.in';
      fout = 'distincte.out';
      nmax = 100000;
      mm = 666013;

type  v = array[1..3] of longint;
      vect = array[1..nmax] of v;
var aib, poz,rez : array[1..nmax] of longint;
    sir,q : vect;
    n,k,m:longint;

procedure citire;
var i:longint;
begin
assign(input,fin); reset(input);
readln(n,k,m);
for i:=1 to n do
        begin
        readln(sir[i][1]);
        sir[i][2]:=i;
        end;
for i:=n downto 1 do
        begin
        if poz[sir[i,1]] <> 0 then
                sir[i,3]:=poz[sir[i,1]]
        else    sir[i,3]:=n+1;
        poz[sir[i,1]]:=i;
        end;
for i:=1 to m do
        begin
        q[i][1]:=i;
        readln(q[i][2], q[i][3]);
        end;
close(input);
end;

procedure QuickSort(var A: vect; Lo, Hi: longint);

procedure Sort(l, r: longint);
var
  i, j, x : longint;
  y : v;
begin
  i := l; j := r; x := a[(l+r) DIV 2][3];
  repeat
    while a[i][3] > x do i := i + 1;
    while x > a[j][3] do j := j - 1;
    if i <= j then
    begin
      y := a[i]; a[i] := a[j]; a[j] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then Sort(l, j);
  if i < r then Sort(i, r);
end;

begin {QuickSort};
  Sort(Lo,Hi);
end;

procedure insert(i, val : longint);
begin
while i <= n do
        begin
        aib[i]:=(aib[i]+val) mod mm;
        i:=i + ( (i xor (i-1) ) and  i ) ;
        end;
end;

function query (i : longint):longint;
var rez: longint;
begin
rez:=0;
while i  > 0 do
        begin
        rez:=(rez + aib[i]) mod mm;
        i:=i - ( (i xor ( i-1) ) and i ) ;
        end;
query:=rez;
end;


procedure calc;
var pozpc,i,r : longint;
begin
pozpc:=1;
for i:=1 to m do
        begin
        while (pozpc <= n ) and (  sir[pozpc][3] > q[i][3] ) do
                begin
                insert(sir[pozpc][2], sir[pozpc][1]);
                inc(pozpc);
                end;
        r:=query(q[i][3]) - query(q[i][2] - 1);
        while r < 0 do inc(r,mm);
        rez[q[i][1]]:=r;
        end;
end;

procedure afis;
var i:longint;
begin
assign(output,fout); rewritE(output);
for i:=1 to m do
        writeln(rez[i]);
close(output);
end;

begin
citire;
quicksort(sir,1,n);
quicksort(q,1,m);
calc;
afis;
end.