#include <fstream>
#include <algorithm>
using namespace std;

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

#define MAXN 100100
#define mod 666013

struct squery {
    int st, fn, poz;
};

squery q[MAXN];
int n, m, arb[MAXN], v[MAXN], last[MAXN], ans[MAXN];

void update(int k, int add) {
    if (k == 0)
        return;
    while(k <= n) {
        arb[k] += add;
        k += k & (-k);
    }
}

int query(int k) {
    int sum = 0;
    while (k > 0) {
        sum += arb[k];
        k -= k & (-k);
    }
    return sum;
}

bool cmp(squery a, squery b) {
    return a.fn < b.fn;
}

int main() {
    int i, j;
    fin >> n >> i >> m;
    for (i = 1; i <= n; ++i)
        fin >> v[i];
    for (i = 1; i <= m; ++i) {
        fin >> q[i].st >> q[i].fn;
        q[i].poz = i;
    }
    sort(q + 1, q + m + 1, cmp);
    for (i = 1, j = 1; i <= m; ++i) {
        while (j <= q[i].fn) {
            update (last[v[j]], -v[j]);
            update (j, v[j]);
            last[v[j]] = j;
            ++j;
        }
        ans[q[i].poz] = query (q[i].fn) - query (q[i].st - 1);
    }
    for (i = 1; i <= m; ++i)
        fout << ans[i] % mod << "\n";
    fout.close();
    return 0;
}