#include <bits/stdc++.h>
using namespace std;

const int kMod = 666013;

struct BIT {
    int n;
    vector<long long> aib;

    BIT(vector<int>& v) : n(int(v.size()) - 1), aib(v.size()) {
        build(v);
    }

    long long query(int i) {
        long long ans = 0;
        for (; i > 0; i -= lsb(i)) {
            ans += aib[i];
        }
        return ans;
    }

    void update(int i, int x) {
        for (; i <= n; i += lsb(i)) {
            aib[i] += x;
        }
    }

private:
    void build(vector<int>& v) {
        for (int i = 1; i <= n; ++i) {
            aib[i] += v[i];
            if (i + lsb(i) <= n) aib[i + lsb(i)] += aib[i];
        }
    }

    static int lsb(int x) {
        return (x & (-x));
    }
};

struct Query {
    int l, r, id;
    long long ans;
};

signed main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
#endif

    int n, k, m; cin >> n >> k >> m;
    vector<int> v(n + 1);
    vector<Query> queries(m + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }

    sort(queries.begin() + 1, queries.end(), [](Query a, Query b) {
        return a.r < b.r;
    });

    vector<int> pos(n + 1);
    BIT aib(pos);

    int ans = 0;
    vector<int> last(k + 1);
    for (int i = 1, idx = 1; i <= n && idx <= m; ++i) {
        if (last[v[i]]) aib.update(last[v[i]], -v[i]);
        aib.update(i, v[i]);
        last[v[i]] = i;
        while (idx <= m && queries[idx].r == i) {
            queries[idx].ans = aib.query(i) - aib.query(queries[idx].l - 1);
            ++idx;
        }
    }

    sort(queries.begin() + 1, queries.end(), [](Query a, Query b) {
        return a.id < b.id;
    });

    for (int i = 1; i <= m; ++i) {
        cout << queries[i].ans % 666013 << '\n';
    }

    return 0;
}