#include <bits/stdc++.h>

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");
const long long mod = 666013;
struct Query {
    long long st, dr, ind;
} q[100002];
long long n, m, k, i, j, x[100002], a[100002], ult[100002];
long long r[100002];

static inline long long Ub(long long a) {
    return (a & -a);
}

static inline void Add(long long poz, long long val) {
    for(long long i = poz; i <= n; i += Ub(i)) a[i] = (a[i] + val) % mod;
}

static inline long long Sum(long long poz) {
    long long sum = 0;
    for(long long i = poz; i >= 1; i -= Ub(i)) sum = (sum + a[i]) % mod;
    return sum;
}

static inline bool Cmp(Query a, Query b) {
    return (a.dr < b.dr);
}

int main() {
    fin >> n >> k >> m;
    for(i = 1; i <= n; i++) fin >> x[i];
    for(i = 1; i <= m; i++) {
        fin >> q[i].st >> q[i].dr;
        q[i].ind = i;
    }

    sort(q + 1, q + m + 1, Cmp);

    j = 1;
    for(i = 1; i <= n && j <= m; i++) {
        Add(i, x[i]);

        if(ult[x[i]]) Add(ult[x[i]], -x[i]);

        ult[x[i]] = i;

        while(q[j].dr == i && j <= m) {
            r[q[j].ind] = (Sum(i) - Sum(q[j].st - 1) + mod) % mod;
            j++;
        }
    }

    for(i = 1; i <= m; i++) fout << r[i] << "\n";

    return 0;
}