#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("distincte.in");
ofstream cout("distincte.out");
int start,n,m,k,aib[100001],mod=666013,sol[10001];
struct per{
    int st,dr,ind;
}q[100001];
int a[10001],fr[100001];
void update(int poz, int val){
    for(int i=poz;i<=n;i+=i&(-i)){
        aib[i]=(aib[i]+val)%mod;

        if(aib[i]<0)
            aib[i]+=mod;
    }
}
int query(int poz){
    int s=0;
    for(int i=poz;i>=1;i-=i&(-i)){
        s+=aib[i];
        s=s%mod;
    }
    return s;
}
bool cmp(per a, per b){
    if(a.dr==b.dr)
        return a.st<b.st;
    return a.dr<b.dr;
}
int main(){
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>q[i].st>>q[i].dr;
        q[i].ind=i;
    }
    sort(q+1,q+m+1,cmp);
    start=1;
    for(int kk=1;kk<=m;kk){
        for(int st=start;st<=q[kk].dr;st++){
            if(fr[a[st]])
                update(fr[a[st]],-a[st]);
            fr[a[st]]=st;
            update(st,a[st]);

        }
        int nr=query(q[kk].dr)-query(q[kk].st-1);
        if(nr<mod)
            nr+=mod;
        sol[q[kk].ind]=nr;
    }
    for(int i=1;i<=n;i++)
        cout<<sol[i];
}