#include <bits/stdc++.h>

using namespace std;

const int MOD = 666013;
struct Vertex {
    Vertex *l, *r;
    int sum;

    Vertex (int val) : l (nullptr), r (nullptr), sum (val) {}
    Vertex (Vertex *l, Vertex *r) : l (l), r (r), sum (0) {
        if (l)
            sum += l->sum;
        if (r)
            sum += r->sum;
        sum %= MOD;
    }
};

int get_sum (Vertex* v, int tl, int tr, int l, int r) {
    if(v == nullptr) return 0;
    if (l > r)
        return 0LL;
    if (l == tl && tr == r)
        return v->sum;
    int tm = (tl + tr) / 2;
    return (get_sum (v->l, tl, tm, l, min (r, tm) )
           + get_sum (v->r, tm + 1, tr, max (l, tm + 1), r)) % MOD;
}

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

int32_t main() {
    ifstream cin ("distincte.in");
    ofstream cout ("distincte.out");

    int n, m, k;
    cin >> n >> k >> m;
    vector<int>zerovec(n);
    vector<int>last(k + 1, -1);

    vector<Vertex*>aint (n);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (i == 0) {
            aint[0] = new Vertex(nullptr, nullptr);
            aint[0] = update (aint[0], 0, n - 1, i, x);
        } else {
            aint[i] = update (aint[i - 1], 0, n - 1, i, x);
        }
        if(last[x] != -1)
            aint[i] = update(aint[i], 0, n - 1, last[x], 0);
        last[x] = i;
    }
    for(int i = 0; i < m; ++i)
    {
        int l, r;
        cin >> l >> r;
        cout << get_sum(aint[r - 1], 0, n - 1, l - 1, r - 1) << '\n';
    }
}