#include <fstream>
#include <vector>

using namespace std;

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

constexpr int MOD = 666013;

vector<vector<pair<int, int>>> queries;
vector<int> values, segTree, lastIndex, answer;

void update(int node, int left, int right, int pos, int val) {
    if (right < pos || left > pos)
        return;

    if (left == right) {
        segTree[node] = val;
        return;
    }

    int mid = (left + right) / 2;
    update(2 * node, left, mid, pos, val);
    update(2 * node + 1, mid + 1, right, pos, val);

    segTree[node] = (segTree[2 * node] + segTree[2 * node + 1]) % MOD;
}

int query(int node, int left, int right, int a, int b) {
    if (left > b || right < a)
        return 0;
    if (left >= a && right <= b)
        return segTree[node];

    int mid = (left + right) / 2;
    return (query(2 * node, left, mid, a, b) +
           query(2 * node + 1, mid + 1, right, a, b)) % MOD;
}

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

    values.resize(n);
    for (int& it : values)
        fin >> it;

    queries.resize(n);
    for (int i = 0;i < m;++i) {
        int left, right;
        fin >> left >> right;
        queries[left - 1].emplace_back(right - 1, i);
    }

    answer.resize(m, 0);
    lastIndex.resize(k + 1, 0);
    segTree.resize(4 * n + 1);

    for (int i = n - 1;i >= 0;--i) {
        if (lastIndex[values[i]])
            update(1, 1, n, lastIndex[values[i]] + 1, 0);
        update(1, 1, n, i + 1, values[i]);
        lastIndex[values[i]] = i;

        for (const auto& q : queries[i])
            answer[q.second] = query(1, 1, n, i + 1, q.first + 1);
    }

    for (const int& it : answer)
        fout << it << '\n';

    return 0;
}