#include <bits/stdc++.h>

using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
#define int long long
int n, m, k, blockSize;
int v[100003], frq[100003], rez[100003];
int sum = 0;

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

inline int cmpMo(Iris &a, Iris &b) {
    int blockA = a.st / blockSize;
    int blockB = b.st / blockSize;
    if(blockA != blockB) return blockA < blockB;
    if(blockA % 2 == 0) return a.dr < b.dr;
    return a.dr > b.dr;
}

inline void add(int x) {
    frq[x]++;
    if(frq[x] == 1) sum += x;
}

inline void remove(int x) {
    frq[x]--;
    if(frq[x] == 0) sum -= x;
}

signed main()
{
    fin >> n >> k >> m, blockSize = (int)sqrt(n);
    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, cmpMo);
    int mo_st = 1, mo_dr = 0;
    for(int i=1; i<=m; i++) {
        int st = query[i].st, dr = query[i].dr;
        while(mo_st < st) remove(v[mo_st++]);
        while(mo_st > st) add(v[--mo_st]);
        while(mo_dr > dr) remove(v[mo_dr--]);
        while(mo_dr < dr) add(v[++mo_dr]);
        rez[query[i].idx] = sum % 666013;
    }
    for(int i=1; i<=m; i++) fout << rez[i] << '\n';

    return 0;
}