#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream cin("distincte.in");
ofstream cout("distincte.out");

long long aib[200005],v[200005],rez[100005],pozant[100005];
int n,k,q;

struct intrebare{
    int l,r,pos;
};

intrebare intb[100005];

void upd(int pos,long long val) {
    for(int i=pos;i<=n;i+=i&-i)
        aib[i]+=val;
}

long long qr(int pos){
    long long s=0;
    for (int i=pos;i>0;i-=i&-i)
        s+=aib[i];
    return s;
}
bool comp(intrebare a,intrebare b){
    return a.r<b.r;
}

int main(){
    int poz=0;
    cin>>n>>k>>q;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    for(int i=0;i<q;i++) {
        cin>>intb[i].l>>intb[i].r;
        intb[i].pos=i;
    }
    sort(intb,intb+q,comp);
    for(int i=0;i<q;i++){
        while(poz<intb[i].r){
            poz++;
            if(pozant[v[poz]]!=0)
                upd(pozant[v[poz]],-v[poz]);
            upd(poz,v[poz]);
            pozant[v[poz]]=poz;
        }
        rez[intb[i].pos]=(qr(intb[i].r)-qr(intb[i].l-1))%666013;
    }
    for(int i=0;i<q;i++)
        cout<<rez[i]<<'\n';
    return 0;
}