#include<bits/stdc++.h>
const int NMAX = 100000, MOD = 666013;
long long aint[NMAX*4+4],ans[NMAX+4],last[NMAX+4],v[NMAX+4];
std::vector<std::pair<int,int>>queries[100001];
void update(int nod, int st, int dr, int pos, int val)
{
    if(st==dr) aint[nod]=val;
        else
        {
            int med=(st+dr)>>1;
            if(pos<=med) update(2*nod,st,med,pos,val);
                else update(2*nod+1,med+1,dr,pos,val);
            aint[nod]=aint[2*nod]+aint[2*nod+1];
        }
}
long long query(int nod, int st, int dr, int stt, int drr)
{
    if(stt<=st && dr<=drr) return aint[nod];
        else
        {
            int med=(st+dr)>>1;
            if(drr<=med) return query(2*nod,st,med,stt,drr);
                else if(stt>med) return query(2*nod+1,med+1,dr,stt,drr);
            return query(2*nod,st,med,stt,drr)+query(2*nod+1,med+1,dr,stt,drr);
        }
}
int main()
{
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    int n,m,k;
    scanf("%d%d%d",&n,&k,&m);
    for(register int i=1;i<=n;i++)
        scanf("%lld",&v[i]);
    for(register int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        queries[y].push_back({x,i});
    }
    for(register int i=1;i<=n;i++)
    {
        update(1,1,n,i,v[i]);
        if(last[v[i]]!=0) update(1,1,n,last[v[i]],0);
        last[v[i]]=i;
        for(register int j=0;j<queries[i].size();j++)
            ans[queries[i][j].second] = query(1,1,n,queries[i][j].first,i) % MOD;
    }
    for(register int i=1;i<=m;i++)
        printf("%lld\n",ans[i]);
    return 0;
}