#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 1e5 + 5;
const int MOD = 666013;

struct Type {
    int lo, hi, idx;
}query[NMax];

int BIT[NMax];
int v[NMax];
int ans[NMax];
int lastSeen[NMax];

inline bool cmp(const Type &a, const Type &b) {
    return a.hi < b.hi;
}

inline void Update(int pos, const int &value, const int &n) {
    for(; pos <= n; pos += (pos & -pos)) {
        BIT[pos] = (BIT[pos] + value) % MOD;
    }
}

inline int Query(int pos) {
    int sum = 0;
    for(; pos > 0; pos -= (pos & -pos)) {
        sum = (sum + BIT[pos]) % MOD;
    }

    return sum;
}

int main() {
    int n, k, m;
    fin >> n >> k >> m;

    for(int i = 1; i <= n; i++) fin >> v[i];
    for(int i = 1; i <= m; i++) {
        int a, b;
        fin >> a >> b;

        query[i] = {a, b, i};
    }

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

    memset(lastSeen, -1, sizeof(lastSeen));

    int now = 1;
    for(int i = 1; i <= n; i++) {
        if(lastSeen[v[i]] != -1)
            Update(lastSeen[v[i]], -v[i], n);

        lastSeen[v[i]] = i;
        Update(i, v[i], n);

        while(now <= m && i == query[now].hi) {
            ans[query[now].idx] = (Query(query[now].hi) - Query(query[now].lo - 1)) % MOD;
            now++;
        }
    }

    for(int i = 1; i <= m; i++) {
        while(ans[i] < 0) ans[i] += MOD;
        fout << ans[i] << "\n";
    }
    return 0;
}