#include <bits/stdc++.h>

using namespace std;

ifstream fin ("distincte.in");
ofstream fout ("distincte.out");

const int nmax=100003;
const int mod=666013;

struct tt{
    int a,b,c;
}v[nmax];

int n,kk,mm,aib[nmax],m[nmax],f[nmax],k=1,sol[nmax];

int lsb(int q){
    return q & -q;
}

void update(int q, int qq){
    while(q<=n){
        aib[q]=(aib[q]+qq)%mod;
        if(aib[q]<0)aib[q]+=mod;
        q+=lsb(q);
    }
}

int query(int q){
    int sum=0;
    while(q){
        sum=(sum+aib[q])%mod;
        q-=lsb(q);
    }
    return sum;
}

bool sortf(tt q, tt qq){
    return q.b<qq.b || (q.b == qq.b && q.a<qq.a);
}

int main()
{
    int a,b;
    fin>>n>>kk>>mm;
    for(int i=1;i<=n;++i){
        fin>>m[i];
    }
    for(int i=1;i<=mm;++i){
        fin>>v[i].a>>v[i].b;
        v[i].c=i;
    }
    sort(v+1,v+mm+1,sortf);
    for(int i=1;i<=n;++i){
        if(f[m[i]])update(f[m[i]],-m[i]);
        update(i,m[i]);
        f[m[i]]=i;
        while(v[k].b==i && k<=mm){
            sol[v[k].c]=query(v[k].b)-query(v[k].a-1);
            if(sol[v[k].c]<0)sol[v[k].c]+=mod;
            k++;
        }
    }
    for(int i=1;i<=mm;++i)fout<<sol[i]<<'\n';
    return 0;
}