#include <stdio.h>
#include <algorithm>
#define lim 100005
#define mod 666013
using namespace std;
int v[lim],aib[lim],last[lim],ans[lim],n;
struct elem{int st,dr,poz;};
elem ask[lim];
bool cmp(elem a,elem b){return a.dr<b.dr;}
int zeros(int x){return (x&(x-1))^x;}
void update(int poz,int val){
    while(poz<=n){
        aib[poz]=(aib[poz]+val+mod)%mod;
        poz+=zeros(poz);
    }
}
int query(int poz){
    int s=0;
    while(poz>0){
        s=(s+aib[poz])%mod;
        poz-=zeros(poz);
    }
    return s;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("distincte.in","r");
    fout=fopen("distincte.out","w");
    int i,k,m;
    fscanf(fin,"%d%d%d",&n,&k,&m);
    for(i=1;i<=n;i++)
        fscanf(fin,"%d",&v[i]);
    for(i=1;i<=m;i++){
        fscanf(fin,"%d%d",&ask[i].st,&ask[i].dr);
        ask[i].poz=i;
    }
    sort(ask+1,ask+m+1,cmp);
    k=1;
    for(i=1;i<=n;i++){
        update(i,v[i]);
        if(last[v[i]]>0)
            update(last[v[i]],-v[i]);
        last[v[i]]=i;
        while(k<=m&&ask[k].dr==i){
            ans[ask[k].poz]=(query(ask[k].dr)-query(ask[k].st-1)+mod)%mod;
            k++;
        }
    }
    for(i=1;i<=m;i++)
        fprintf(fout,"%d\n",ans[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}