#include <fstream>
#include <iostream>
#include <algorithm>
#define NMAX 100005
#define MOD 666013
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
struct query {
    int st, dr, ind;
    long long ans;
};
int N, M, K;
int v[NMAX], lastAp[NMAX];
long long aib[NMAX];
query q[NMAX];
bool compByRight(query a, query b) {
    if (a.dr == b.dr) {
        return a.st < b.st;
    }
    return a.dr < b.dr;
}
bool compByInd(query a, query b) {
    return a.ind < b.ind;
}
void read() {
    fin >> N >> K >> M;
    for (int i = 1; i <= N; ++i) {
        fin >> v[i];
    }
    for (int i = 1; i <= M; ++i) {
        fin >> q[i].st >> q[i].dr;
        q[i].ind = i;
    }
}
void update(int poz, int val) {
    for (int i = poz; i <= N; i += i & -i) {
        aib[i] += val;
    }
}
int query(int poz) {
    int sum = 0;
    for (int i = poz; i > 0; i -= i & -i) {
        sum += aib[i];
    }
    return sum;
}
int main()
{
    read();
    sort(q + 1, q + M + 1, compByRight);
    int nrQ = 1;
    for (int i = 1; i <= N; ++i) {
        if (lastAp[v[i]]) {
            update(lastAp[v[i]], -v[i]);
        }
        lastAp[v[i]] = i;
        update(i, v[i]);
        while (q[nrQ].dr == i) {
            q[nrQ].ans = query(q[nrQ].dr) - query(q[nrQ].st - 1);
            nrQ++;
        }
    }
    sort(q + 1, q + M + 1, compByInd);
    for (int i = 1; i <= M; ++i) {
        fout << q[i].ans % MOD << "\n";
    }
    return 0;
}