#include <fstream>

using namespace std;

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

const int MOD = 666013;
int n, m, k;
vector<int> v, last_idx, ans;
vector<vector<pair<int, int>>> queries;

class Segment_Tree {
    vector<int> tree;
    int size;
    void _update(int node, int left, int right, int pos, int val) {
        if (left == right) {
            tree[node] = val;
            return;
        }
        int middle = (left + right) / 2;
        if (pos <= middle) {
            _update(2 * node, left, middle, pos, val);
        } else {
            _update(2 * node + 1, middle + 1, right, pos, val);
        }
        tree[node] = (tree[2 * node] + tree[2 * node + 1]) % MOD;
    }
    void _query(int node, int left, int right, int query_left, int query_right, int &ans) {
        if (query_left <= left && right <= query_right) {
            ans = (ans + tree[node]) % MOD;
            return;
        }
        int middle = (left + right) / 2;
        if (query_left <= middle) {
            _query(2 * node, left, middle, query_left, query_right, ans);
        }
        if (middle < query_right) {
            _query(2 * node + 1, middle + 1, right, query_left, query_right, ans);
        }
    }
public:
    Segment_Tree(int size) {
        this->size = size;
        tree.assign(4 * size + 2, 0);
    }
    void update(int pos, int val) {
        _update(1, 1, size, pos, val);
    }
    void query(int query_left, int query_right, int &ans) {
        _query(1, 1, size, query_left, query_right, ans);
    }
};

int main() {
    cin >> n >> k >> m;
    v.assign(n + 2, 0);
    ans.assign(m + 2, 0);
    last_idx.assign(k + 2, 0);
    queries.assign(n + 2, vector<pair<int, int>>());
    for (int i = 1 ; i <= n ; ++i) {
        cin >> v[i];
    }
    for (int i = 1 ; i <= m ; ++i) {
        int query_start, query_finish;
        cin >> query_start >> query_finish;
        queries[query_finish].push_back({query_start, i});
    }
    Segment_Tree t(n);
    for (int query_finish = 1 ; query_finish <= n ; ++query_finish) {
        if (last_idx[v[query_finish]] != 0) {
            t.update(last_idx[v[query_finish]], 0);
        }
        t.update(query_finish, v[query_finish]);
        last_idx[v[query_finish]] = query_finish;
        for (auto [query_start, query_idx] : queries[query_finish]) {
            int sum = 0;
            t.query(query_start, query_finish, sum);
            ans[query_idx] = sum;
        }
    }
    for (int i = 1 ; i <= m ; ++i) {
        cout << ans[i] << "\n";
    }
    return 0;
}