#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 100000;
const int MOD = 666013;
struct BIT {
    vector <long long> bit;
    int N;

    void init(int N) {
        this->N = N;
        bit.resize(N + 1);
    }

    inline static int lsb(int x) {
        return (x ^ (x - 1)) & x;
    }

    long long query(int pos) {
        long long ret = 0;
        for(; pos >= 1; pos -= lsb(pos)) {
            ret += bit[pos];
        }
        return ret;
    }

    void update(int pos, int val) {
        for(; pos <= N; pos += lsb(pos)) {
            bit[pos] += val;
        }
    }
};

BIT T;
int N, M, K;
int A[N_MAX + 5];
int last[N_MAX + 5];
long long ans[N_MAX + 5];
vector < pair<int, int> > queries[N_MAX + 5];

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

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K >> M;
    for(int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    for(int i = 1; i <= M; i++) {
        int x, y;
        cin >> x >> y;
        queries[y].push_back(make_pair(x, i));
    }

    T.init(N);
    for(int i = 1; i <= N; i++) {
        if(last[A[i]] != 0) {
            T.update(last[A[i]], -A[i]);
        }
        last[A[i]] = i;
        T.update(i, A[i]);

        for(auto it : queries[i]) {
            ans[it.second] = (T.query(i) - T.query(it.first - 1)) % MOD;
        }
    }

    for(int i = 1; i <= M; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}