#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;

inline void update_tree( int position, int value ) {
    for( int i = position; i <= N; i += (i & (-i)) ) {
        AIB[i] += value;

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

inline int query_tree( int position ) { int value = 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 () {

    freopen( "distincte.in" ,"r", stdin  );
    freopen( "distincte.out","w", stdout );

    scanf( "%d %d %d", &N, &K, &M );
    for( int i = 1; i <= N; i ++ )
        scanf( "%d", &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 ++ ) {
        scanf( "%d %d", &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 ) {
            update_tree( Point[ptx].x, Point[ptx].z );
            ptx --;
        }

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

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

    return 0;
}