#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1, mod = 666013;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
#define cin fin
#define cout fout
struct node{
    long long sm = 0;
    node* l, *r;
    node(int val) : sm(val), l(nullptr), r(nullptr) {}
    node(node*l, node* r) : sm(0), l(l), r(r){
        if(l){
            sm = (sm + l->sm) % mod;
        }
        if(r){
            sm = (sm + r->sm) % mod;
        }
    }
};

node* build(int tl, int tr){
    if(tl == tr){
        return new node(0);
    }
    int tm = (tl + tr) / 2;
    return new node(build(tl, tm), build(tm + 1, tr));
}
node* update(node* v, int tl, int tr, int pos, int val){
    if(tl == tr){
        return new node(val);
    }
    int tm = (tl + tr) / 2;
    if(pos <= tm) return new node(update(v->l, tl, tm, pos, val), v->r);
    else return new node(v->l, update(v->r, tm + 1, tr, pos, val));

}
int query(node* v, int tl, int tr, int l, int r){
    if(l <= tl && r >= tr){
        return v->sm;
    }
    if(tr < l || tl > r) return 0;
    int tm = (tl + tr) / 2;
    int smq = query(v->l, tl, tm, l, r);
    int sm1 = query(v->r, tm + 1, tr, l, r);
    return (smq + sm1) % mod;
}
vector<node*> roots(N);
int n, k, q, v[N], fr[N];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
    }
    roots[0] = build(1, n);
    for(int i = 1; i <= n; i++){
        roots[i] = update(roots[i - 1], 1, n, i, v[i]);
        if(fr[v[i]] == 0){
            fr[v[i]] = i;
        }else{
            roots[i] = update(roots[i], 1, n, fr[v[i]], 0);
            fr[v[i]] = i;
        }
    }

    for(int i = 1; i <= q; i++){
        int l, r;
        cin >> l >> r;
        cout << query(roots[r], 1, n, l, n) << '\n';
    }
}