#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 666013
#define LSB(x) (x&(-x))
using namespace std;
int n,m,k,dr,st,p,ras,prec[100004],ok[100004],a[100004],urm[100004],raspuns[100004],aib[400004];
struct qry
{
    int st,dr,p;
}q[100004];
bool cmp(qry x, qry y)
{
    if(x.dr==y.dr && x.st==y.st)return x.p<y.p;
    if(x.dr==y.dr) return x.st<y.st;
    return x.dr>y.dr;
}
void update(int poz, int val)
{
    for(int i=poz;i<=n;i+=LSB(i))
        aib[i]=(aib[i]+val)%mod;
}
int  query(int poz)
{
    int ras=0;
    for(int i=poz;i>0;i-=LSB(i))
        ras=(ras+aib[i])%mod;
    return ras;
}
int main()
{
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    scanf("%d %d %d",&n,&k,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        prec[i]=0;
        if(ok[a[i]]>0)
        {
            urm[ok[a[i]]]=i;
            prec[i]=ok[a[i]];
            ok[a[i]]=0;
        }
        ok[a[i]]=i;
    }
    for(int i=1;i<=k;i++)
        if(ok[i]>0)
        {
            urm[ok[i]]=n+1;
            update(ok[i],i);
            ok[i]=0;
        }
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&st, &dr);
        q[i].st=st;
        q[i].dr=dr;
        q[i].p=i;
    }
    sort(q+1,q+m+1,cmp);
    p=n;
    for(int i=1;i<=m;i++)
    {
        dr=q[i].dr;
        st=q[i].st;
        while(p>dr)
        {
            if(prec[p]>0)update(prec[p],a[prec[p]]);
            p--;
        }
        ras=query(dr);
        ras-=query(st-1);
        if(ras<0)ras+=mod;
        raspuns[q[i].p]=ras;
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",raspuns[i]);
    return 0;
}