#include <bits/stdc++.h>

using namespace std;

ifstream f("distincte.in");
ofstream g("distincte.out");

const int NMAX = 100005;
const int mod = 666013;
int n,m,k,v[NMAX], aib[NMAX],ans[NMAX],pos[NMAX];
pair < pair < int, int > , int> q[NMAX];

void add(int pos, int val){

    while(pos <= n){

        aib[pos] = ( (aib[pos] + val) % mod + mod) % mod;
        pos += pos & -pos;

    }

}

int sum(int pos){
    int s = 0;

    while(pos > 0){

        s = (s + aib[pos]) % mod;
        pos -= pos & -pos;

    }

    return s;

}

bool cmp(pair < pair < int, int>, int > X, pair < pair < int, int >,  int > Y){
    return X.first.second < Y.first.second;
}

int main(){
    int i, j;

    f >> n >> k >> m;

    for(i = 1 ; i <= n ; i++){

        f >> v[i];

    }

    for(i = 1 ; i <= m ; i++){

        f >> q[i].first.first >> q[i].first.second;
        q[i].second = i;

    }

    sort(q + 1, q + m + 1, cmp);

    int last = 0;
    for(i = 1 ; i <= m ; i++){

        while(last < q[i].first.second){

            last++;

            if(pos[v[last]])
                add(pos[v[last]], -v[last]);

            pos[v[last]] = last;
            add(last, v[last]);
        }

        ans[q[i].second] = (sum(q[i].first.second) - sum(q[i].first.first - 1) + mod) % mod;
    }

    for(i = 1 ; i <= m ; i++)
        g << ans[i] << "\n";

    return 0;
}