#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;
const int NMAX = 100000, MOD = 666013;

struct pack {
    int hi, ind;
};

int aib[NMAX + 1], sums[NMAX + 1], ans[NMAX];
int nextPos[NMAX + 1], lastAp[NMAX + 1], nr[NMAX + 1];
bool ap[NMAX + 1];
vector<pack> his[NMAX + 1];

inline int query( int pos);
inline void update(int pos, int n, int val);

int main() {
    int n, m, k, i, j, lo, hi, len;
    FILE *fin = fopen("distincte.in", "r");

    fscanf(fin, "%d%d%d", &n, &k, &m);
    for (i = 1; i <= n; i++) {
        fscanf(fin, "%d", &nr[i]);
        sums[i] += sums[i - 1] + nr[i];
        if (sums[i] >= MOD)
            sums[i] -= MOD;
        if (ap[nr[i]])
            update(i, n, nr[i]);
        ap[nr[i]] = 1;
    }
    for (i = n; i > 0; i--) {
        nextPos[i] = lastAp[nr[i]];
        lastAp[nr[i]] = i;
    }

    for (i = 0; i < m; i++) {
        fscanf(fin, "%d%d", &lo, &hi);
        his[lo].push_back({hi, i});
    }
    fclose(fin);

    for (i = 1; i <= n; i++) {
        len = his[i].size();
        for (j = 0; j < len; j++) {
            pack tmp = his[i][j];
            ans[tmp.ind] = sums[tmp.hi] - sums[i - 1] - query(tmp.hi);
            if (ans[tmp.ind] < 0)
                ans[tmp.ind] += MOD;
        }

        if (nextPos[i])
            update(nextPos[i], n, -nr[i]);
    }

    FILE *fout = fopen("distincte.out", "w");
    for (i = 0; i < m; i++)
        fprintf(fout, "%d\n", ans[i]);

    return 0;
}

inline int query(int pos) {
    long long s = 0;
    for (; pos; pos -= (pos & -pos)) {
        s += aib[pos];
        if (s >= MOD)
            s -= MOD;
    }
    return s;
}
inline void update(int pos, int n, int val) {
    for (; pos <= n; pos += (pos & -pos)) {
        aib[pos] += val;
        if (aib[pos] >= MOD)
            aib[pos] -= MOD;
        else if (aib[pos] < 0)
            aib[pos] += MOD;
    }
}