#include <iostream>
#include <fstream>
#include <vector>

#define NMAX 100010
#define MOD 666013

using namespace std;

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

long long a[NMAX], ST[4 * NMAX], pre[NMAX], nxt[NMAX];

void update(int node, int l, int r, int arrayIndex, long long value) {
    if (l == r) {
        ST[node] = a[arrayIndex] = value;
        return;
    }
    int middle = (l + r) >> 1;
    if (arrayIndex <= middle) {
        update(2 * node + 1, l, middle, arrayIndex, value);
    } else {
        update(2 * node + 2, middle + 1, r, arrayIndex, value);
    }
    ST[node] = (MOD + ST[2 * node + 1] + ST[2 * node + 2]) % MOD;
}

long long query(int node, int l, int r, int queryLeft, int queryRight) {
    if (l >= queryLeft && queryRight >= r) {
        return ST[node];
    }
    // if intersection is null, return -INF
    if (queryLeft > r || queryRight < l) {
        return 0;
    }
    // if intersection is partial, return the maximum of the two queries
    int middle = (l + r) / 2;
    return (MOD + query(2 * node + 1, l, middle, queryLeft, queryRight) +
                 query(2 * node + 2, middle + 1, r, queryLeft, queryRight)) % MOD;
}

int main()
{
    int n, k, m;
    fin >> n >> k >>  m;
    for (int i = 0; i < n; ++i) {
        fin >> a[i];
    }

    vector<vector<pair<long long, long long>>> queries(n);

    for (int i = 0; i < m; ++i){
        int l, r;
        fin >> l >> r;
        queries[l - 1].push_back({r - 1, i});
    }


    vector<int> lastIndex(k + 1, 0);
    vector<long long> answer(m);

    for (int i = n - 1; i >= 0; --i) {
        if (lastIndex[a[i]]) {
            update(0, 0, n - 1, lastIndex[a[i]], 0);
        }
        lastIndex[a[i]] = i;
        update(0, 0, n - 1, i, a[i]);
        for (auto queryEnding : queries[i]) {
            answer[queryEnding.second] = query(0, 0, n - 1, i, queryEnding.first);
        }
    }

    for (int i = 0; i < m; ++i) {
        fout << answer[i] % MOD << "\n";
    }
    return 0;
}