#include <bits/stdc++.h>
#define dbg(x) cerr << #x << ' ' << x << '\n'
#define dbgsp(x) cerr << #x << ' ' << x << ' '

using namespace std;

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

const int N = 1e5;
const int MOD = 666013;

class Fenwick {
private:
    vector <long long> a;
    int _n;

    int lsb(int i) {
        return (i & (-i));
    }

public:
    Fenwick(int n) {
        a.resize(1 + n);
        _n = n;
    }

    void update(int pos, int value) {
        for (int i = pos; i <= _n; i += lsb(i)) {
            a[i] += value;
        }
    }

    int query(int pos) {
        int ans = 0;
        for (int i = pos; i > 0; i -= lsb(i)) {
            ans += a[i];
            ans %= MOD;
        }

        return ans;
    }
};

struct Query {
    int x, y, pos;

    bool operator < (const Query &aux) const {
        if (y == aux.y)
            return x < aux.x;
        return y < aux.y;
    }
};

int main() {
    int n, m, k;
    in >> n >> k >> m;
    Fenwick aib(1 + n);

    vector <int> v(1 + n), lastpos(1 + k), ans(m);
    vector <Query> q(m);

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

    for (int i = 0; i < m; i++) {
        in >> q[i].x >> q[i].y;
        q[i].pos = i;
    }

    sort(q.begin(), q.end());

    vector <Query>::iterator it = q.begin();
    for (int i = 1; i <= n; i++) {
        if (lastpos[v[i]])
            aib.update(lastpos[v[i]], -v[i]);
        aib.update(i, v[i]);
        lastpos[v[i]] = i;

        while (it != q.end() && (*it).y == i) {
            ans[(*it).pos] = (aib.query(i) - aib.query((*it).x - 1) + MOD) % MOD;
            assert(ans[(*it).pos] >= 0);
            ++it;
        }
    }

    for (auto i : ans)
        out << i << '\n';
    return 0;
}