#include <bits/stdc++.h>
#define MN 107171

using namespace std;

int F[MN], n, k, m, V[MN], R[MN], rez;
tuple<int, int, int> Q[MN];

static inline void add(const int &p) {
    if(!(F[V[p]]++)){
        rez += V[p];
        if(rez > 666012) rez -= 666013;
    }
}
static inline void rem(const int &p) {
    if(!(--F[V[p]])){
         rez -= V[p];
         if(rez < 0) rez += 666013;
    }
}
int main() {
    ifstream fi("distincte.in");
    ofstream fo("distincte.out");
    fi >> n >> k >> m;
    for(int i = 1; i <= n; ++i) fi >> V[i];
    for(int i = 1; i <= m; ++i) {
        fi >> get<0>(Q[i]) >> get<1>(Q[i]);
        get<2>(Q[i]) = i;
    }
    int rad = (int)(.5 + sqrt(double(n)));
    sort(Q+1, Q+m+1, [&](auto a, auto b) {
        if((get<0>(a) / rad) != (get<0>(b) / rad))
            return (get<0>(a) / rad) < (get<0>(b) / rad);
        return bool((get<1>(a) < get<1>(b)) ^ (((get<0>(a) / rad) & 1)));
    });
    int st = 1, dr = 0;
    for(int i = 1; i <= m; ++i) {
        auto [l, r, id] = Q[i];
        while(dr < r) add(++dr);
        while(dr > r) rem(dr--);
        while(st < l) rem(st++);
        while(l < st) add(--st);
        R[id] = rez;
    }
    for(int i = 1; i <= m; ++i) fo << R[i] << "\n";
    return 0;
}