#include <bits/stdc++.h>

using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
#define int long long
const int MOD = 666013;
int n, m, k, last[100003];
int v[100003], aib[100003], rez[100003];

struct Iris {
    int st, dr, idx;
}query[100003];

inline int cmp(Iris &a, Iris &b) { return a.dr < b.dr; }

inline void updateAIB(int x, int val) {
    for(int i=x; i<=n; i+=(i&(-i))) aib[i] += val;
}

inline int queryAIB(int x) {
    int rez = 0;
    for(int i=x; i>=1; i-=(i&(-i))) rez += aib[i];
    return rez;
}

signed main()
{
    fin >> n >> k >> m;
    for(int i=1; i<=n; i++) fin >> v[i];
    for(int i=1; i<=m; i++) {
        fin >> query[i].st >> query[i].dr;
        query[i].idx = i;
    }
    sort(query+1, query+m+1, cmp);
    int idx = 1;
    for(int i=1; i<=m; i++) {
        int st = query[i].st, dr = query[i].dr;
        while(idx <= dr) {
            if(last[v[idx]] == 0) {
                ///e prima data cand intalnesc v[idx]
                updateAIB(idx, v[idx]);
                last[v[idx]] = idx;
            }
            else {
                ///am mai intalnit => o sterg unde o aveam si o pun aici ; e optim s o tin cat mai la dreapta
                updateAIB(last[v[idx]], -v[idx]);
                updateAIB(idx, v[idx]);
                last[v[idx]] = idx;
            }
            idx++;
        }
        rez[query[i].idx] = (queryAIB(dr) - queryAIB(st - 1) + MOD) % MOD;
    }
    for(int i=1; i<=m; i++) fout << rez[i] << '\n';

    return 0;
}