var
  Szamok, Kov, Bin: array[1..100000] of longint;
  n, k, m, i, j, x, y, r, poz: longint;
  f, g: text;

procedure FelTolt;
var
  i, j: longint;
begin
  for i := 1 to n do
    ReadLn(f, Szamok[i]);
  for i := 1 to n do
    for j := i - (i xor (i and (i - 1))) + 1 to i do
      Bin[i] := (Bin[i] + Szamok[j]) mod 666013;
end;

begin
  Assign(f, 'distincte.in');
  Assign(g, 'distincte.out');
  Reset(f);
  ReWrite(g);

  ReadLn(f, n, k, m);
  Feltolt;
  for i := 1 to n do
    begin
      j := i + 1;
      while (Szamok[i] <> Szamok[j]) and (j <> n + 1) do
        Inc(j);
      Kov[i] := j;
    end;

  for i := 1 to m do
    begin
      r := 0;
      ReadLn(f, x, y);
      poz := y;
      while poz > 0 do
        begin
          r := r + Bin[poz];
          poz := poz - (poz xor (poz and (poz - 1)));
        end;

      poz := x - 1;
      while poz > 0 do
        begin
          r := r - Bin[poz];
          poz := poz - (poz xor (poz and (poz - 1)));
        end;

      for j := x to y do
        begin
          if kov[j] <= y then r := r - Szamok[j];
          if r < 0 then r := r + 666013;
        end;
      WriteLn(g, r);
    end;
  Close(f);
  Close(g);
end.