#include <bits/stdc++.h>

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

int N, K, M, nrP, nrQ, X, Y, Next[DIM], Answer[DIM], V[DIM];

struct point{ int x, y, s; } P[DIM];
struct query{ int x, y, p, t; } Q[DIM << 1];

class input_reader {
    private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        char buffer[SIZE]; int cursor;

        inline void advance() {
            if( ++cursor == SIZE ) {
                cursor = 0;
                fread( buffer, SIZE, 1, input_file );
            }

            return;
        }

        inline char current() {
            return buffer[cursor];
        }
    public:
        input_reader( const char *file_name, const char *file_type ) {
            input_file = fopen( file_name, file_type ); cursor = 0;
            fread( buffer, SIZE, 1, input_file );
        }

        input_reader &operator >>( int &value ) {
            value = 0;

            while( current() < '0' || current() > '9' )
                advance();

            while( current() >= '0' && current() <= '9' ) {
                value = value * 10 + ( current() - '0' );
                advance();
            }

            return *this;
        }
} input_file( "distincte.in", "r" );
FILE *output_file = fopen( "distincte.out", "w" );

class nrx_bit {
    private:
        static const int SIZE = 1 << 17;
        static const int MOD  = 666013;
        int my_bit[SIZE];
    public:
        inline void update_bit( int pos, int val ) {
            for( int i = pos; i < SIZE; i += (i & (-i)) )
                my_bit[i] = ( my_bit[i] + val ) % MOD;
            return;
        }

        inline int query_bit( int pos ) { int val = 0;
            for( int i = pos; i > 0; i -= (i & (-i)) )
                val = ( val + my_bit[i] ) % MOD;
            return val;
        }

        inline int bit_size() {
            return SIZE;
        }
} my_bit;

inline bool cmp1( point A, point B ) {
    return A.x > B.x;
}

inline bool cmp2( query A, query B ) {
    return A.x > B.x;
}

int main() {

    input_file >> N >> K >> M;

    for( int i = 1; i <= N; i ++ ) {
        input_file >> V[i];
        Next[i] = N + 1;
    }

    for( int i = N; i >= 1; i -- ) {
        P[++nrP] = { i, Next[ V[i] ], V[i] };
        Next[ V[i] ] = i;
    }

    for( int i = 1; i <= M; i ++ ) {
        input_file >> X >> Y;
        Q[++nrQ] = { X, Y + 1, i, 1 };
        Q[++nrQ] = { Y + 1, Y + 1, i, 2 };
    }

    sort( P + 1, P + nrP + 1, cmp1 );
    sort( Q + 1, Q + nrQ + 1, cmp2 );

    for( int i = 1, cursor = 0; i <= nrQ; i ++ ) {
        while( cursor < nrP && P[cursor + 1].x >= Q[i].x ) {
            cursor ++;
            my_bit.update_bit( P[cursor].y, P[cursor].s );
        }

        switch( Q[i].t )  {
            case 1: {
                Answer[ Q[i].p ] += ( my_bit.query_bit( N + 1 ) - my_bit.query_bit( Q[i].y - 1 ) + MOD ) % MOD;
                break;
            }
            case 2: {
                Answer[ Q[i].p ] -= ( my_bit.query_bit( N + 1 ) - my_bit.query_bit( Q[i].y - 1 ) + MOD ) % MOD;
                break;
            }
        }
    }

    for( int i = 1; i <= M; i ++ )
        fprintf( output_file, "%d\n", ( Answer[i] + MOD ) % MOD );

    return 0;
}