#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 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() {

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

    fscanf( input_file, "%d %d %d", &N, &K, &M );

    for( int i = 1; i <= N; i ++ ) {
        fscanf( input_file, "%d", &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 ++ ) {
        fscanf( input_file, "%d %d", &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( my_bit.bit_size() - 1 ) - my_bit.query_bit( Q[i].y - 1 );
                break;
            }
            case 2: {
                Answer[ Q[i].p ] -= my_bit.query_bit( my_bit.bit_size() - 1 ) - my_bit.query_bit( Q[i].y - 1 );
                break;
            }
        }
    }

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

    return 0;
}