#include <bits/stdc++.h>
using namespace std;

int last[100005];
struct thing{
    int l, r, i;
}Q[100005];
int v[100005];
int ans[100005];
int aib[100005];
const int MOD = 666013;
int n;

void update(int p, int x){
    for(;p <= n;p += p&(-p)){
        aib[p] = (aib[p] + x + MOD)%MOD;
    }
}

int query(int p){
    int ret = 0;
    for(;p;p -= p&(-p)){
        ret = (ret + aib[p])%MOD;
    }
    return ret;
}

bool comp(thing a, thing b){
    return a.r < b.r;
}

int main()
{
    int k,q,i,j;
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
    scanf("%d %d %d", &n, &k, &q);
    for(i = 1;i <= n;i++){
        scanf("%d", &v[i]);
    }
    for(i = 1;i <= q;i++){
        scanf("%d %d", &Q[i].l, &Q[i].r);
        Q[i].i = i;
    }
    sort(Q + 1, Q + q + 1, comp);
    for(i = 1;i <= q;i++){
        for(j = Q[i - 1].r + 1;j <= Q[i].r;j++){
            if(last[v[j]]){
                update(last[v[j]], -v[j]);
            }
            update(j, v[j]);
            last[v[j]] = j;
        }
        ans[Q[i].i] = (query(Q[i].r) - query(Q[i].l - 1) + MOD)%MOD;
    }
    for(i = 1;i <= q;i++){
        printf("%d\n", ans[i]);
    }
    return 0;
}