const
        FIN = 'distincte.in';
        FOUT = 'distincte.out';
        NMAX = 100000;
        PRIM = 666013;

  VAR
      A, SEL : array[ 1..NMAX ] of longint;
      N, M, i, j, curent, k, x, y, aux, sum : longint;
      f, g : text;

  begin
   assign( f, FIN ); reset( f ); readln( f, n, k, m );
   assign( g, FOUT ); rewrite( g );
   for  i := 1 to N do readln( f, A[i] );
   for i := 1 to M do
     begin
       readln( f, x, y ); if x > y then begin aux := x; x := y; y := aux; end;
       curent := i; sum := 0;
       for j := x to y do
        if sel[ A[j] ] <> curent then begin sel[ A[j] ] := curent;
                                            sum := sum + A[j];
                                            if sum >= prim then dec( sum, prim );
                                        end;
       writeln( g, sum );
    end;
   close( f );
   close( g );
  end.