#include<fstream>
#include<algorithm>

using namespace std;

ifstream fin( "distincte.in" ); ofstream fout( "distincte.out" );

const int nmax = 1e5;
const int mod = 666013;
int n;
int v[ nmax + 1 ], last_poz[ nmax + 1 ];
int aib[ nmax + 1 ], sol[ nmax + 1 ];

struct query{
    int x, y, ind;

    inline bool operator < ( const query &a ) const {
        return ( y < a.y );
    }
} q[ nmax + 1 ];

inline int lsb( int x ) {
    return ( x & -x );
}
void update( int pos, int val ) {
    for( int i = pos; i <= n; i += lsb( i ) ) {
        aib[ i ] = (aib[ i ] + val) % mod;
        if ( aib[ i ] < 0 ) {
            aib[ i ] += mod;
        }
    }
}
int query( int pos ) {
    int ans = 0;
    for( int i = pos; i > 0; i -= lsb( i ) ) {
        ans += aib[ i ];
        if ( ans >= mod ) {
            ans -= mod;
        }
    }
    return ans;
}
int main() {
    int m, k;
    fin >> n >> k >> m;
    for( int i = 1; i <= n; ++ i ) {
        fin >> v[ i ];
    }
    for( int i = 0; i < m; ++ i ) {
        fin >> q[ i ].x >> q[ i ].y;
        q[ i ].ind = i;
    }
    sort( q, q + m );
    int ind = 1;
    for( int i = 0; i < m; ++ i ) {
        while ( ind <= q[ i ].y ) {
            if ( last_poz[ v[ ind ] ] != 0 ) {
                update( last_poz[ v[ ind ] ], -v[ ind ] );
            }
            update( ind, v[ ind ] );
            last_poz[ v[ ind ] ] = ind;
            ++ ind;
        }
        sol[ q[ i ].ind ] = (query( q[ i ].y ) - query( q[ i ].x - 1 ) + mod) % mod;
    }
    for( int i = 0; i < m; ++ i ) {
        fout << sol[ i ] << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}