# include <algorithm>
# include <iostream>
# include <fstream>

# include <cstring>

using namespace std;

const int MAX_N = 100000;
const int MOD = 666013;

class aib
{
private:
    int n;
    int *v;

public:
    aib( int _n ) {
        n = _n;
        v = new int[1 + n];
        memset( v, 0, sizeof( v ) );
    }

    void add( int pos, int nr ) {
        while ( pos <= n ) {
            v[pos] = ( v[pos] + nr % MOD + MOD ) % MOD;
            pos += ( pos & -pos );
        }
    }

    int operator[]( int pos ) {
        int s = 0;
        while ( pos > 0 ) {
            s = ( s + v[pos] ) % MOD;
            pos -= ( pos & -pos );
        }
        return s;
    }
};

struct query {
    int ans, i, j;

    query() { }

    query( int a, int b, int c ) {
        ans = a;
        i = b;
        j = c;
    }

    bool operator < ( const query &a ) const {
        return j < a.j;
    }
} q[MAX_N];

int v[1 + MAX_N];
aib s( MAX_N );
int ans[MAX_N];
int f[1 + MAX_N];

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

    int n, k, m;
    fin >> n >> k >> m;

    for ( int i = 1; i <= n; i ++ )
        fin >> v[i];

    for ( int i = 0; i < m; i ++ ) {
        int a, b;
        fin >> a >> b;

        q[i] = query( i, a, b );
    }

    sort( q, q + m );

    int p = 0;
    for ( int i = 1; i <= n; i ++ ) {
        if ( !f[v[i]] )
            s.add( f[v[i]] = i, v[i] );
        else {
            s.add( f[v[i]], -v[i] );
            s.add( f[v[i]] = i, v[i] );
        }

        while ( p < m && q[p].j == i ) {
            ans[q[p].ans] = ( s[i] - s[q[p].i - 1] + MOD ) % MOD;
            p ++;
        }
    }

    for ( int i = 0; i < m; i ++ )
        fout << ans[i] << '\n';

    fin.close();
    fout.close();

    return 0;
}