#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 1e5;
const int MOD = 666013;

struct Query {
    int l , r , pos;
    bool operator <( const Query &a ) const {
        return l < a.l;
    }
} queries[MAXN + 1];
int v[MAXN + 1] , aib[MAXN + 1] , idx[MAXN + 1] , ans[MAXN + 1] , n;
vector< int >pos[MAXN + 1];
void update( int pos , int val ) {
    for( ; pos <= n ; pos += pos & -pos )
        aib[pos] += val;
}
int query( int pos ) {
    int ans = 0;
    for( ; pos ; pos -= pos & -pos )
        ans += aib[pos];
    return ans;
}
signed main() {
    ifstream cin( "distincte.in" );
    ofstream cout( "distincte.out" );
    int k , q , i , st;
    cin >> n >> k >> q;
    for( i = 1 ; i <= n ; i++ ) {
        cin >> v[i];
        if( pos[v[i]].empty() ) {
            idx[i] = 0;
            update( i , v[i] );
        }
        pos[v[i]].push_back( i );
    }
    for( i = 1 ; i <= q ; i++ ) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].pos = i;
    }
    sort( queries + 1 , queries + q + 1 );
    i = 1;
    for( st = 1 ; st <= n ; st++ ) {
        while( i <= q && queries[i].l == st ) {
            ans[queries[i].pos] = query( queries[i].r );
            i++;
        }
        update( st , -v[st] );
        idx[v[st]]++;
        if( idx[v[st]] < pos[v[st]].size() )
            update( pos[v[st]][idx[st]] , v[st] );
    }
    for( i = 1 ; i <= q ; i++ )
        cout << ans[i] % MOD << '\n';
    return 0;
}