#include <bits/stdc++.h>
using namespace std;

string fileName = "distincte";
ifstream fin(fileName + ".in");
ofstream fout(fileName + ".out");

long long t[100001];
long long last[100001], n, m, k, v[100001];
long long res[100001];
const int mod = 666013;

inline void add(int pos, int val) {

    for (int i = pos; i <= n; i += (i & -i))
        t[i] += val;
}

inline long long get(int pos) {

    long long s = 0;
    for (int i = pos; i; i -= (i & -i))
        s += t[i];
    return s;
}

struct query {
    long long pos, i, j;

    bool operator<(const query &aux) const {
        return j < aux.j;
    }
} q[100001];

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].i >> q[i].j, q[i].pos = i;

    sort(q + 1, q + m + 1);
    k = 1;
    long long total = 0;

    for (int i = 1; i <= n; i++) {

        if (!last[v[i]]) {

            last[v[i]] = i;
            add(i, v[i]);
            total += v[i];
        }
        else {

            add(last[v[i]], -v[i]);
            last[v[i]] = i;
            add(i, v[i]);
        }

        while (k <= m && q[k].j == i) {

            res[q[k].pos] = total - get(q[k].i - 1);
            k++;
        }
    }

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

    return 0;
}