#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int N = 1e5;
const int MOD = 666013;

struct question{
    int l, r, index;
};

int n, m, k;
int aib[N + 5], v[N + 5], ans[N + 5], last[N + 5];
question q[N + 5];

bool comp(question a, question b) {
    if (a.r == b.r)
        return a.l < b.l;
    return a.r < b.r;
}

int lsb(int x) {
    return x & -x;
}

void update(int pos, int val) {
    for (int i = pos; i <= n; i += lsb(i))
        aib[i] = (aib[i] + val) % MOD;
}

int query(int pos) {
    int sum = 0;
    for (int i = pos; i >= 1; i -= lsb(i))
        sum = (sum + aib[i]) % MOD;
    return sum;
}

int main() {
    in >> n >> k >> m;
    for (int i = 1; i <= n; i++)
        in >> v[i];
    for (int i = 1; i <= m; i++) {
        in >> q[i].l >> q[i].r;
        q[i].index = i;
    }
    sort(q + 1, q + m + 1, comp);
    int x = 1;
    for (int i = 1; i <= n; i++) {
        if (last[v[i]] != 0)
            update(last[v[i]], -v[i]);
        update(i, v[i]);
        last[v[i]] = i;
        //cout << i << ' ' << v[i] << ": " << query(2) << ' ' << query(3) << '\n';
        while (q[x].r == i) {
            ans[q[x].index] = query(q[x].r) - query(q[x].l - 1);
            x++;
        }
    }
    for (int i = 1; i <= m; i++)
        out << ans[i] << '\n';
    return 0;
}