#include<stdio.h>
#include<algorithm>
using namespace std;

#define ll long long
#define MOD 666013

struct inter
{
    int x,y,z;
    ll sol;
};
inter q[100005];
int v[100005],n,m,k,inc;
int urm[100005],f[100005];
ll arb[1<<18];

void update(int n,int l,int r,int poz,int val)
{
    if(l==r)
    {
        arb[n]=val;
        return ;
    }
    int mij=(l+r)/2;
    if(poz<=mij)
        update(2*n,l,mij,poz,val);
    else
        update(2*n+1,mij+1,r,poz,val);
    arb[n]=arb[2*n]+arb[2*n+1];
}

ll query(int n,int l,int r,int a,int b)
{
    if(a<=l && r<=b)
        return arb[n];
    int mij=(l+r)/2;
    ll s=0;
    if(a<=mij)
        s+=query(2*n,l,mij,a,b);
    if(b>mij)
        s+=query(2*n+1,mij+1,r,a,b);
    return s;
}

int cmp(inter a,inter b)
{
    return (a.y<b.y);
}

int cmp2(inter a,inter b)
{
    return (a.z<b.z);
}

int main ()
{
    int i;
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    scanf("%d%d%d",&n,&k,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        update(1,1,n,i,v[i]);
    }
    for(i=1;i<=n;i++)
    {
        urm[i]=f[v[i]];
        f[v[i]]=i;
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].x,&q[i].y);
        q[i].z=i;
    }
    sort(q+1,q+m+1,cmp);
    inc=1;
    for(i=1;i<=n;i++)
    {
        if(urm[i])
            update(1,1,n,urm[i],0);
        while(inc<=m && q[inc].y==i)
        {
            q[inc].sol=query(1,1,n,q[inc].x,q[inc].y);
            inc++;
        }
    }
    sort(q+1,q+m+1,cmp2);
    for(i=1;i<=m;i++)
        printf("%lld\n",(q[i].sol)%MOD);
    return 0;
}