#include <fstream>
#include <vector>
using namespace std;

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

#define NMAX 100005
#define MOD 666013

int v[NMAX];
int last[NMAX];
int rez[NMAX];
int aib[NMAX];
vector<pair<int, int>> q[NMAX];

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

int query(int poz) {
    int rez = 0;
    for (int i = poz; i >= 1; i -= i & (-i)) {
        rez += aib[i];
        rez %= MOD;
    }
    return rez;
}

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

    for (int i = 1; i <= n; ++i) {
        if (last[v[i]]) {
            update(last[v[i]], -v[i], n);
        }
        update(i, v[i], n);
        last[v[i]] = i;
        for (auto it : q[i]) {
            rez[it.first] = (query(i) - query(it.second - 1) + MOD) % MOD;
        }
    }

    for (int i = 1; i <= m; ++i) {
        fout << rez[i] << '\n';
    }
    return 0;
}