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

using namespace std;

typedef long long ll;

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

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

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

int n, m, k;
int v[N + 5], last[N + 5];
ll aib[N + 5], ans[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, ll val) {
    for (int i = pos; i <= n; i += lsb(i))
        aib[i] = (aib[i] % MOD + val % MOD) % MOD;
}

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

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;
        while (q[x].r == i) {
            ans[q[x].index] = (query(q[x].r) - query(q[x].l - 1)) % MOD;
            x++;
        }
    }
    for (int i = 1; i <= m; i++)
        out << ans[i] % MOD << '\n';
    return 0;
}