#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>

using namespace std;

struct Query {
    int l, r, idx;
};

const int MOD = 666013;

vector<int> arr;
vector<int> answer;
unordered_map<int, int> freq;
int currentSum = 0;
void add(int x) {
    if (freq[x] == 0) {
        currentSum = (currentSum + x) % MOD;
    }
    freq[x]++;
}
void remove(int x) {
    if (freq[x] == 1) {
        currentSum = (currentSum - x + MOD) % MOD;
    }
    freq[x]--;
}
int main() {
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
    int N, K, M;
    cin >> N >> K >> M;
    arr.resize(N + 1);
    for (int i = 1; i <= N; ++i)
        cin >> arr[i];
    vector<Query> queries(M);
    for (int i = 0; i < M; ++i) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].idx = i;
    }
    answer.resize(M);
    int blockSize = sqrt(N);
    sort(queries.begin(), queries.end(), [blockSize](Query a, Query b) {
        if (a.l / blockSize != b.l / blockSize)
            return a.l / blockSize < b.l / blockSize;
        return a.r < b.r;
    });
    int currentL = 1, currentR = 0;
    for (const auto &q : queries) {
        while (currentR < q.r) add(arr[++currentR]);
        while (currentR > q.r) remove(arr[currentR--]);
        while (currentL < q.l) remove(arr[currentL++]);
        while (currentL > q.l) add(arr[--currentL]);
        answer[q.idx] = currentSum;
    }
    for (int i = 0; i < M; ++i)
        cout << answer[i] << "\n";
    return 0;
}