#include<cstdio>
#include<algorithm>
#define MAX 100000
#define mod 666013
#define m(i) i&(-i)
using namespace std;

struct mazi{int st,dr,rasp,p;};

int v[MAX+1];
int aib[MAX+1];
int ap[MAX+1];
int n;

mazi q[MAX+1];

bool meow1(mazi a,mazi b){
    if (a.dr<b.dr) return true;
    return false;
}

bool meow2(mazi a,mazi b){
    if (a.p<b.p) return true;
    return false;
}


void update(int i,int x){
    for(;i<=n;i+=m(i)){
        aib[i]+=x;
        if (aib[i]>=mod) aib[i]-=mod;
        else
        if (aib[i]<0) aib[i]+=mod;
    }
}


int query(int i){
    int s=0;

    for(;i>0;i-=m(i)){
        s=s+aib[i]-mod;
        if (s<0) s+=mod;
    }

    return s;
}


int main(){
    freopen ("distincte.in","r",stdin);
    freopen ("distincte.out","w",stdout);
    int m,k,i,j;
    int s;

    scanf ("%d%d%d",&n,&k,&m);

    for(i=1;i<=n;i++)
        scanf ("%d",&v[i]);

    for(i=1;i<=m;i++){
        scanf ("%d%d",&q[i].st,&q[i].dr);
        q[i].p=i;
    }

    sort(q+1,q+m+1,meow1);

    j=1;
    s=0;
    for(i=1;i<=m;i++){
        while(j<=q[i].dr){
            if (ap[v[j]]==0){
                s=s+v[j]-mod;
                if (s<0) s+=mod;
            }
            else {
                update(ap[v[j]],-v[j]);
            }

            ap[v[j]]=j;
            update(j,v[j]);
            j++;
        }

        q[i].rasp=s-query(q[i].st-1);
        if (q[i].rasp<0) q[i].rasp+=mod;
    }

    sort(q+1,q+m+1,meow2);

    for(i=1;i<=m;i++)
        printf ("%d\n",q[i].rasp);

    return 0;
}