#include <bits/stdc++.h>

using namespace std;
#define ll long long
ll cans;
int ap[100005];
int v[100005];

void add(int pos){
    ap[v[pos]]++;
    if(ap[v[pos]] == 1){
        cans += v[pos];
    }
}

void rem(int pos){
    ap[v[pos]]--;
    if(ap[v[pos]] == 0){
        cans -= v[pos];
    }
}

struct query{
    int l, r, i;
}Q[100005];
int ans[100005];
const int BLOCK = 331;

bool comp(query a, query b){
    if(a.l/BLOCK == b.l/BLOCK){
        return a.r < b.r;
    }
    return a.l < b.l;
}
int main()
{
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
    int i,n,k,q,j;
    scanf("%d %d %d", &n, &k, &q);
    for(i = 1;i <= n;i++){
        scanf("%d", &v[i]);
        add(i);
    }
    for(i = 1;i <= q;i++){
        scanf("%d %d", &Q[i].l, &Q[i].r);
        Q[i].i = i;
    }
    int cL, cR;
    cL = 1;
    cR = n;
    sort(Q + 1, Q + q + 1, comp);
    for(i = 1;i <= q;i++){
        int L, R;
        L = Q[i].l;
        R = Q[i].r;
        for(j = cL;j < L;j++){
            rem(j);
        }
        for(j = cL - 1;j >= L;j--){
            add(j);
        }
        cL = L;
        for(j = cR + 1;j <= R;j++){
            add(j);
        }
        for(j = cR;j > R;j--){
            rem(j);
        }
        cR = R;
        ans[Q[i].i] = cans%666013;
    }
    for(i = 1;i <= q;i++){
        printf("%lld\n", ans[i]);
    }
    return 0;
}