program disticnte;
var
  f, g: text;
  n, k, m, a, b, r, i, j: longint;
  Szam: array[0..100000] of longint;
  Sum: array[1..100000,1..100000] of longint;
  BooleM: array[1..100000] of boolean;

Procedure Init;
var i: longint;
begin
  for i := 1 to k do
    BooleM[i] := false;
end;

begin
  Assign(f, 'distincte.in');
  Reset(f);
  ReadLn(f, n, k, m);
  for i := 1 to n do ReadLn(f, Szam[i]);

  for i := 1 to n do
    begin
      Init;
      for j := i to n do
        begin
          if i = j then Sum[i,j] := Szam[i]
          else
            If BooleM[Szam[j]] then Sum[i,j] := Sum[i,j - 1]
            else Sum[i,j] := (Sum[i, j - 1] + Szam[j]) mod 666013;
          BooleM[Szam[j]] := true;
        end;
    end;

    Assign(g, 'distincte.out');
    ReWrite(g);
    for i := 1 to m do
      begin
        ReadLn(f, a, b);
        WriteLn(g, Sum[a,b]);
      end;
  Close(f);
  Close(g);
end.