{
        Problema distincte
}

Program distincte;

Const MAXN = 100000;
      MODULO  = 666013;

Type vector = array[0..MAXN] of Longint;
     vizitare = array[1..MAXN] of 0..1;

Var v, max : vector;
    viz : vizitare;
    n, k, m, i, j, p, s : Longint;

Begin
    Assign( input, 'distincte.in' );
    Reset( input );
        Readln( n, k, m );
        max[0] := 0;
        For i := 1 to n do
            Begin
                Readln( v[i] );
                if v[i] > max[i-1] then max[i] := v[i]
                                   else max[i] := max[i-1];
            End;
    Assign( output, 'distincte.out' );
    Rewrite( output );
        While m > 0 do
        Begin
            Readln( i, j );
            For p := 1 to max[j] do viz[p] := 0;
            s := 0;
            For p := i to j do
                if viz[v[p]] = 0 then
                    Begin
                        s := ( s + v[p] ) mod MODULO;
                        viz[v[p]] := 1;
                    End;
            m := m-1;
            Writeln( s );
        End;
    Close( input );
    Close( output );
End.