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

using namespace std;
const int NMAX = 100000;

struct pack {
    int hi, ind;
};

long long 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 long long 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] + (long long)nr[i];
        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 (nextPos[i])
            update(nextPos[i], n, -nr[i]);
    }

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

    return 0;
}

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