#include <fstream>
#include <algorithm>

using namespace std;

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

const int nmax = 1e5, mod = 666013;
int n, nrq, k, a[nmax + 2], lastt[nmax + 2];

int addmod(int x, int64_t y){
    x += y;
    if(x >= mod)
        x -= mod;
    return x;
}

struct query{
    int lf, rg, qidx;
    bool operator < (const query &obj) const {
        return lf > obj.lf;
    }
} queries[nmax + 2];
int answer[nmax + 2];

inline int f(int x){ return (x & (-x)); }
struct fenwicktree{
    int64_t tree[nmax + 2];

    void add(int pos, int val){
        for(int i = pos; i <= n; i += f(i))
            tree[i] += val;
    }

    int sum(int pos){
        int s = 0;
        for(int i = pos; i >= 1; i -= f(i))
            s = addmod(s, tree[i]);
        return s;
    }
} aib;

int main(){

    in>>n>>k>>nrq;
    for(int i = 1; i <= n; i++)
        in>>a[i], lastt[a[i]] = n + 1;

    for(int i = 1; i <= nrq; i++){
        in>>queries[i].lf>>queries[i].rg;
        queries[i].qidx = i;
    }

    sort(queries + 1, queries + 1 + nrq);

    int idx = 1;
    for(int i = n; i >= 1; i--){
        aib.add(lastt[a[i]], -a[i]);
        aib.add(i, a[i]); lastt[a[i]] = i;

        for(; idx <= nrq && queries[idx].lf == i; idx++)
            answer[queries[idx].qidx] = aib.sum(queries[idx].rg);
    }

    for(int i = 1; i <= nrq; i++)
        out<<answer[i]<<"\n";

    return 0;
}