#include <fstream>
#include <algorithm>

using namespace std;

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

const int DIM = 100010;
const int MOD = 666013;

int n, k, m;
int v[DIM], aib[DIM], f[DIM], Sol[DIM];
struct interval {;
    int x, y, ind;
} q[DIM];

bool cmp(interval a, interval b) {
    if (a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

void update(int pos, int val) {
    for (int i = pos; i <= n; i += (i & -i)) {
        aib[i] += val;
        aib[i] %= MOD;
    }
}

int query(int pos) {
    int s = 0;
    for (int i = pos; i > 0; i -= (i & -i)) {
        s += aib[i];
        s %= MOD;
    }
    return s;
}

int main() {
    fin >> n >> k >> m;
    for (int i = 1; i <= n; i++)
        fin >> v[i];
    for (int i = 1; i <= m; i++){
        fin >> q[i].x >> q[i].y;
        q[i].ind = i;
    }

    sort(q + 1, q + m + 1, cmp);

    int start = 1;
    for (int i = 1; i <= m; i++) {
        int finish = q[i].y;
        for (int j = start; j <= finish; j++) {
            if (f[v[j]] == 0) {
                update(j, v[j]);
                f[v[j]] = j;
            } else {
                update(f[v[j]], -v[j]);
                f[v[j]] = j;
                update(j, v[j]);
            }
        }

        int sol = query(finish) - query(q[i].x - 1);
        if (sol < 0)
            sol += MOD;
        Sol[q[i].ind] = sol;
        start = finish + 1;
    }

    for (int i = 1; i <= m; i++)
        fout << Sol[i] << '\n';

    return 0;
}