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

using namespace std;
const int NMAX = 100010, 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);

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

int main() {
    int n, m, k, i, j, lo, hi, len;

    fin >> n >> k >> m;
    for (i = 1; i <= n; i++) {
        fin >> 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++) {
        fin >> lo >> hi;
        his[lo].push_back({hi, i});
    }

    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);
            while (ans[tmp.ind] < 0)
                ans[tmp.ind] += MOD;
        }

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

    for (i = 0; i < m; i++)
        fout << ans[i] << '\n';

    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;
    }
}