program disticnte;
type rec = record
       hanyadik: array[1..100] of longint;
       db: longint;
       bb: array[1..100] of longint;
     end;
var
  f, g: text;
  n, k, m, a, b, r, i, j, h: longint;
  Szam: array[0..100000] of longint;
  Sum: array[1..100000] of longint;
  BooleM: array[1..100000] of boolean;
  rr: array[1..100000] of longint;
  elso: array[1..10000] of rec;


Procedure Init;
var i: longint;
begin
  for i := 1 to k do BooleM[i] := false;
  for i := 1 to n do Sum[i] := 0;
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 m do
      begin
        ReadLn(f, a, b);
        Inc(elso[a].db);
        elso[a].bb[elso[a].db] := b;
        elso[a].hanyadik[elso[a].db] := i;
      end;

  for i := 1 to n do
    begin
      Init;
      for j := i to n do
        begin
          if i = j then Sum[i] := Szam[i]
          else
            if BooleM[Szam[j]] then Sum[j] := Sum[j - 1] else
            Sum[j] := (Sum[j - 1] + Szam[j]) mod 666013;
           BooleM[Szam[j]] := true;
        end;
      for h := 1 to elso[i].db do
        rr[elso[i].hanyadik[h]] := Sum[elso[i].bb[h]];
    end;

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