#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

constexpr size_t LIM = 100005;
constexpr int MOD = 666013;

struct Query {
    int l, r, i;
} query[LIM];

static inline bool compare(Query q1, Query q2) {
    return q1.r < q2.r || (q1.r == q1.r && q1.l < q2.l);
}

int N, K, M, i, arr[LIM];
int ans[LIM], last[LIM];
long long tree[LIM];

static inline void update(int i, int val) {
    for (; i <= N; i += i & (-i))
        tree[i] += val;
}

static inline long long prefix(int i) {
    long long sum = 0;
    for (; i; i -= i & (-i))
        sum += tree[i];
    return sum;
}

int main() {
    fin >> N >> K >> M;
    for (i = 1; i <= N; ++i) {
        fin >> arr[i];
        update(i, arr[i]);
    }

    for (i = 1; i <= M; ++i) {
        fin >> query[i].l >> query[i].r;
        query[i].i = i;
    }

    sort(query + 1, query + M + 1, compare);

    int r = 1;
    for (i = 1; i <= M; ++i) {
        while (r <= query[i].r) {
            if (last[arr[r]])
                update(last[arr[r]], -arr[r]);
            last[arr[r]] = r;
            ++r;
        }

        ans[query[i].i] = (prefix(query[i].r) - prefix(query[i].l - 1)) % MOD;
    }

    for (i = 1; i <= M; ++i)
        fout << ans[i] << '\n';

    fin.close();
    fout.close();
    return 0;
}