#include <bits/stdc++.h>
using namespace std;
ifstream fin ("distincte.in");
ofstream fout ("distincte.out");
#define int long long

const int MAXN=1e5+10;
const int B=300;
const int MOD=666013;

int n,k,m,a[MAXN],f[MAXN];
int ans[MAXN];
struct query{
    int l,r,i;
}v[MAXN];
bool cmp (query x, query y){
    if (x.l/B==y.l/B) return x.r<y.r;
    return x.l/B<y.l/B;
}
int s;
void add (int pos){
    f[a[pos]]++;
    if (f[a[pos]]==1) s+=a[pos];
}
void del (int pos){
    f[a[pos]]--;
    if (f[a[pos]]==0) s-=a[pos];
}
int q;
signed main()
{
    fin >>n>>k>>q;
    for (int i=1;i<=n;++i){
        fin >>a[i];
    }
    for (int i=1;i<=q;++i){
        fin >>v[i].l>>v[i].r;
        v[i].i=i;
    }
    sort (v+1,v+q+1,cmp);
    int l=1,r=0;
    for (int i=1;i<=q;++i){
        while (r<v[i].r) add (++r);
        while (l>v[i].l) add (--l);
        while (r>v[i].r) del (r--);
        while (l<v[i].l) del (l++);

        ans[v[i].i]=s;
    }

    for (int i=1;i<=q;++i){
        fout <<ans[i]%MOD<<'\n';
    }
    return 0;
}