#include <cstdio>
#include <algorithm>

const int DIM = 1 << 17;
const int MOD = 666013;
using namespace std;

int AIB[DIM], V[DIM], N, M, K, Next[DIM], Sol[DIM];
struct point{ int x, y, z; } Point[DIM]; int X, Y;
struct query{ int st, dr, pos; } Query[DIM]; int ptx;

class InputReader {
    public:
        InputReader() {}
        InputReader(const char *file_name) {
            input_file = fopen(file_name, "r");
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
        inline InputReader &operator >>(int &n) {
            while(buffer[cursor] < '0' || buffer[cursor] > '9') {
                advance();
            }
            n = 0;
            while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
                n = n * 10 + buffer[cursor] - '0';
                advance();
            }
            return *this;
        }
    private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        int cursor;
        char buffer[SIZE];
        inline void advance() {
            ++ cursor;
            if(cursor == SIZE) {
                cursor = 0;
                fread(buffer, SIZE, 1, input_file);
            }
        }
};

inline void update_tree( int position, int value ) {

    if( position == 0 )
        return;

    for( int i = position; i <= N + 1; i += (i & (-i)) ) {
        AIB[i] += value;

        if( AIB[i] >= MOD )
            AIB[i] -= MOD;
    }
    return;
}

inline int query_tree( int position ) { int value = 0;

    if( position == 0 )
        return 0;

    for( int i = position; i >= 1; i -= (i & (-i)) ) {
        value += AIB[i];

        if( value >= MOD )
            value -= MOD;
    }
    return value;
}

inline int CMP1( point A, point B ) {
    return A.y < B.y;
}

inline int CMP2( query A, query B ) {
    return A.dr < B.dr;
}

int main () {

    InputReader fin( "distincte.in" );
    freopen( "distincte.out","w", stdout );

    fin >> N >> K >> M;
    for( int i = 1; i <= N; i ++ )
        fin >> V[i];

    for( int i = 1; i <= K; i ++ )
        Next[i] = N + 1;

    for( int i = N; i >= 1; i -- ) {
        Point[i].x = i;
        Point[i].y = Next[V[i]];
        Point[i].z = V[i];
        Next[V[i]] = i;
    }

    sort( Point + 1, Point + N + 1, CMP1 );

    for( int i = 1; i <= M; i ++ ) {
        fin >> X >> Y;

        Query[i].st = X;
        Query[i].dr = Y;
        Query[i].pos = i;
    }

    sort( Query + 1, Query + M + 1, CMP2 );

    ptx = N;
    for( int i = M; i >= 1; i -- ) {

        while( Point[ptx].y > Query[i].dr && ptx >= 1 ) {
            update_tree( Point[ptx].x, Point[ptx].z );
            ptx --;
        }

        Sol[Query[i].pos] = ( query_tree( Query[i].dr ) - query_tree( Query[i].st - 1 ) + 2 * MOD ) % MOD;
    }

    for( int i = 1; i <= M; i ++ )
        printf( "%d\n", Sol[i] );

    return 0;
}