#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5,MOD = 666013;
long long aib[NMAX + 5];
int v[NMAX + 5],Prev[NMAX + 5];
struct Query {
    long long a,b,poz,ans;
}q[NMAX + 5];
int n;

bool cmp(Query x, Query y) {
    if (x.b == y.b)
        return x.a < y.a;
    return x.b < y.b;
}
bool cmp2(Query x, Query y) {
    return x.poz < y.poz;
}
void update(int poz, int val) {
    for (int i = poz;i <= n;i += (i & (-i)))
        aib[i] += val;
}
long long query(int poz) {
    long long ans = 0;
    for (int i = poz;i > 0;i -= (i & (-i)))
        ans += aib[i];
    return ans;
}
int main()
{
    ifstream fin("distincte.in");
    ofstream fout("distincte.out");
    int k,m,cnt = 0;
    fin >> n >> k >> m;
    memset(Prev, -1, sizeof(Prev));
    for (int i = 1;i <= n;i++)
        fin >> v[i];
    for (int i = 0;i < m;i++) {
        fin >> q[i].a >> q[i].b;
        q[i].poz = i;
    }
    sort(q, q + m, cmp);
    for (int i = 1;i <= n;i++) {
        if (Prev[v[i]] != -1)
            update(Prev[v[i]], -v[i]);
        update(i, v[i]);
        Prev[v[i]] = v[i];
        while (cnt < m && q[cnt].b == i) {
            q[cnt].ans = query(q[cnt].b) - query(q[cnt].a - 1);
            cnt++;
        }
    }
    sort(q, q + m, cmp2);
    for (int i = 0;i < m;i++)
        fout << q[i].ans % MOD << '\n';
    return 0;
}