var
  Szamok, Kov: array[1..100000] of longint;
  IFa: array[1..1000000] of longint;
  n, m, i, j, x, y: longint;
  f, g: text;
  ossz: int64;

procedure FelTolt(p, e, u, a, b: longint);
var
  i, koz: longint;
  su: int64;
begin
  su := 0;
  koz := (e + u) div 2;
  for i := e  to u do su := (su + Szamok[i]) mod 666013;
  IFa[p] := su;
  if e < u then
    if koz >= e then FelTolt(2 * p, e, koz, a, b);
    if koz < u then FelTolt(2 * p + 1, koz + 1, u, a, b);
end;

function Suma(p, e, u, a, b: longint): longint;
var koz: longint;
    sum: int64;
begin
  sum := 0;
  if (a <= e) and (b >= u) then sum := IFa[p]
  else
    begin
      koz := (e + u) div 2;
      if a <= koz then sum := sum + Suma(2 * p, e, koz, a, b);
      if b > koz then sum := sum + Suma(2 * p + 1, koz + 1, u, a, b);
    end;
  Suma := (sum) mod 666013;
end;

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

  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;

  FelTolt(1, 1, n, 1, n);

  for i := 1 to m do
    begin
      ReadLn(f, x, y);
      ossz := Suma(1, 1, n, x, y);
      for j := x to y do
        if kov[j] <= y then ossz := ossz - Szamok[j];
      WriteLn(g, ossz);
    end;
  Close(f);
  Close(g);
end.