#include <bits/stdc++.h>

using namespace std;

#define INFILE "distincte.in"
#define OUTFILE "distincte.out"

typedef long long ll;

const int N_MAX = 1e5 + 5;
const int MOD = 666013;

int n, k, queries;
int v[N_MAX], prevIndex[N_MAX];
ll aint[N_MAX * 6], ans[N_MAX];
vector<pair<int, int> > q[N_MAX];

void update(int node, int left, int right, int position, int value){

    if(left == right){
        aint[node] = value;
        return;
    }

    int middle = (left + right) >> 1;

    if(position <= middle) update(2 * node, left, middle, position, value);
    else update(2 * node + 1, middle + 1, right, position, value);

    aint[node] = (aint[2 * node] + aint[2 * node + 1]) % MOD;

}

ll query(int node, int left, int right, int x, int y){

    if(x <= left && right <= y) return aint[node];

    int middle = (left + right) >> 1;

    ll sum = 0;

    if(x <= middle) sum += query(2 * node, left, middle, x, y);
    if(y > middle) sum += query(2 * node + 1, middle + 1, right, x, y);

    return sum % MOD;

}

void solve(){

    cin >> n >> k >> queries;

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

    for(int i = 1; i <= queries; ++i){
        int left, right; cin >> left >> right;
        q[right].push_back(make_pair(left, i));
    }

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

        update(1, 1, n, i, v[i]);

        if(prevIndex[v[i]] != 0) update(1, 1, n, prevIndex[v[i]], 0);

        prevIndex[v[i]] = i;

        for(auto it : q[i]) ans[it.second] = query(1, 1, n, it.first, i);

    }

    for(int i = 1; i <= queries; ++i) cout << ans[i] << '\n';

}

int main(){
    ios_base::sync_with_stdio(false);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}