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

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

const int MOD = 666013;

class FenTree {
  private:
    int n;
    vector<int> bit;

  public:
    FenTree(int n) :
        n(n), bit(n + 1) { }

    void update(int pos, int val) {
        for (int i = pos; i <= n; i += i & -i) {
            bit[i] += val;
            if (bit[i] >= MOD) bit[i] -= MOD;
        }
    }

    int query(int pos) {
        int sum = 0;
        for (int i = pos; i >= 1; i -= i & -i) {
            sum += bit[i];
            if (sum >= MOD) sum -= MOD;
        }
        return sum;
    }

    int query(int left, int right) {
        int ret = query(right) - query(left - 1);
        if (ret < 0) ret += MOD;
        return ret;
    }
};

int main() {
    int n, k, q;
    fin >> n >> k >> q;

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

    vector<int> next(n + 1), last(k + 1, n + 1);
    for (int i = n; i >= 1; i--) {
        next[i] = last[v[i]];
        last[v[i]] = i;
    }

    vector<int> qry(q);
    vector<vector<int>> left(n + 1), right(n + 1);
    for (int i = 0; i < q; i++) {
        int x, y; fin >> x >> y;
        left[x - 1].push_back(i);
        right[y].push_back(i);
        qry[i] = y;
    }

    vector<int> sol(q);
    FenTree bit(n + 1);
    for (int i = 1; i <= n; i++) {
        bit.update(next[i], v[i]);
        for (int j : left[i])
            sol[j] -= bit.query(qry[j] + 1, n + 1);
        for (int j : right[i]) {
            sol[j] += bit.query(qry[j] + 1, n + 1);
            if (sol[j] < 0) sol[j] += MOD;
        }
    }

    for (int i = 0; i < q; i++)
        fout << sol[i] << '\n';

    fout.close();
    return 0;
}