#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("distincte.in");
ofstream out("distincte.out");
const int DIM = 100001;
int n,m,s,k,hz[DIM],ans[DIM];
long long vect[DIM],aib[DIM];
pair<int, pair<int,int> >op[DIM];
void update_aib( int poz, int val ){
    for( int i = poz; i <= n; i += ( i&(-i) ) ){
        aib[i] = (aib[i] + val+666013)%666013;
    }
    return;
}
int query_aib( int a, int b ){
    int ansa = 0, ansb = 0;
    for( int i = a-1; i >= 1; i -= ( i&(-i) ) ){
        ansa = (ansa+aib[i]+666013)%666013;
    }
    for( int i = b; i >= 1; i -= ( i&(-i) ) ){
        ansb = (ansb+aib[i]+666013)%666013;
    }
    return ansb - ansa;
}
int main(){
    int i;
    in >> n >> k >> m;
    for( i = 1; i <= n; i ++ ){
        in >> vect[i];
    }
    for( i = 1; i <= k ; i ++ ){
        hz[i] = -1;
    }
    for( i = 1; i <= m; i ++ ){
        in >> op[i].second.first >> op[i].first;
        op[i].second.second = i;
    }
    sort( op+1,op+m+1 );
    s = 0;
    for( i = 1; i <= n; i ++ ){
        if( hz[vect[i]] not_eq -1 ){
            update_aib( hz[vect[i]], -vect[i] );
        }
        update_aib( i, vect[i] );
        hz[vect[i]] = i;
        while( op[s+1].first == i and s < m){
            s++;
            ans[op[s].second.second ] = (query_aib( op[s].second.first, op[s].first)+666013) % 666013;
        }
    }
    for( i = 1; i <= m; i ++ ){
        out<<ans[i]<<"\n";
    }
    return 0;
}