#include <bits/stdc++.h>

#define N 100003
#define W 666013

using namespace std;

int n, m, k, a[N], freq[N], sol, rez[N];

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

void add(int i) {
    if (++freq[a[i]] == 1)
        sol = (sol + a[i]) % W;
}

void remove(int i) {
    if (--freq[a[i]] == 0)
        sol = (sol - a[i]) % W;
}

int main() {
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);

    int i;
    scanf("%i%i%i", &n, &k, &m);
    for (i = 1; i <= n; i++)
        scanf("%i", &a[i]);

    double sqrt_n = sqrt(n);
    for (i = 0; i < m; i++) {
        scanf("%i%i", &query[i].l, &query[i].r);
        query[i].i = i;
    }
    sort(query, query + m, [&sqrt_n](const Query &a, const Query &b) -> bool {
        int block_nr_a = a.l / sqrt_n;
        int block_nr_b = b.l / sqrt_n;
        return block_nr_a < block_nr_b || (block_nr_a == block_nr_b && a.r < b.r);
    });

    int l = 1, r = 1; // current segment heads
    sol = a[1]; freq[a[1]] = 1;
    for (i = 0; i < m; i++) {
        while (l < query[i].l) {
            remove(l);
            l++;
        }
        while (l > query[i].l) {
            add(l - 1);
            l--;
        }
        while (r < query[i].r) {
            add(r + 1);
            r++;
        }
        while (r > query[i].r) {
            remove(r);
            r--;
        }
        if (sol < 0) sol = W + sol % W;
        rez[query[i].i] = sol;
    }

    for (i = 0; i < m; i++) printf("%i\n", rez[i]);
    return 0;
}