#include <fstream>
#include <vector>

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 FenwickTree {
    vector<int> tree;
    vector<int> arr;
    int size;
    int query_(int pos) {
        int ans = 0;
        for (int i = pos ; i > 0 ; i -= i & -i) {
            ans = (ans + tree[i]) % MOD;
        }
        return ans;
    }
    void update_(int pos, int val) {
        for (int i = pos ; i <= n ; i += i & -i) {
            tree[i] = (tree[i] + val) % MOD;
        }
    }
public:
    FenwickTree(int size) {
        this->size = size;
        tree.assign(size + 2, 0);
        arr.assign(size + 2, 0);
    }
    void update(int pos, int val) {
        int delta = val - arr[pos];
        update_(pos, delta);
        arr[pos] = val;
    }
    int query(int query_left, int query_right) {
        return query_(query_right) - query_(query_left - 1);
    }
};

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});
    }
    FenwickTree 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]) {
            ans[query_idx] = t.query(query_start, query_finish);
        }
    }
    for (int i = 1 ; i <= m ; ++i) {
        cout << ans[i] << "\n";
    }
}