#include <fstream>
#include <algorithm>

using namespace std;

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

const int nMax = 100005, MOD = 666013;
int v[nMax], n, m, last[nMax], k;
long long sol[nMax], aib[nMax];
pair<pair<int, int>, int> q[nMax];

void Update(int ind, int val) {
    for (int i = ind; i <= n; i += i & (-i))
        aib[i] += val;
}

int Query(int ind) {
    int sum = 0;
    for (int i = ind; i >= 1; i -= i & (-i))
        sum += aib[i];
    return sum;
}

int main() {
    fin >> n >> k >> m;
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
        Update(i, v[i]);
    }
    for (int i = 1; i <= m; i++) {
        fin >> q[i].first.second >> q[i].first.first;
        q[i].second = i;
    }
    sort(q + 1, q + 1 + m);
    int ind = 1;
    for (int i = 1; i <= m; i++) {
        while (ind <= q[i].first.first) {
            if (last[v[ind]] != 0)
                Update(last[v[ind]], -v[ind]);
            last[v[ind]] = ind;
            ind++;
        }
        sol[q[i].second] = Query(q[i].first.first) - Query(q[i].first.second - 1);
    }
    for (int i = 1; i <= m; i++)
        fout << sol[i] % MOD << '\n';
    fin.close();
    fout.close();
    return 0;
}