#include <bits/stdc++.h>

using namespace std;
int ;
struct andreea
{
    int s,d,ind;
}q[100003];
bool cmp(andreea a, andreea b)
{
    if(a.d<b.d)return 0;
    return 1;aint[nod]=aint[nod*2]+aint[nod*2+1];
}
void update(int nod, int st, int dr, int poz, int val)
{
    int mij;
    if(st==dr)
    {
        aint[nod]=val;
        return ;
    }
    mij=(st+dr)/2;
    if(poz<=mij)update(nod*2,st,mij,poz,val);
    else update(nod*2+1,mij+1,dr,poz,val);
    aint[nod]=(aint[nod*2]+aint[nod*2+1])%666013;
}
void query(int nod, int st, int dr, int x, int y)
{
    int mij;
    if(x<=st&&y>=dr)
    {
        sol=sol+aint[nod];
        return ;
    }
    mij=(st+dr)/2;
    if(x<=mij)update(nod*2,st,mij,x,y);
    if(y>=mij+1) update(nod*2+1,mij+1,dr,x,y);
}
int main()
{
    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",&a[i]);
    for(i=1;i<=n;i++)
    {
        prec[i]=v[a[i]];
        v[a[i]]=i;
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].s,&q[i].d);
        q[i].ind=i;
    }
    sort(q+1,q+m+1,cmp);
    for(i=n;i>=1;i--)
    {
        v[i]=0;
    }
    for(i=n;i>=1;i--)
    {
        if(v[a[i]]==0)
        {
            update(1,1,n,i,a[i]);
            v[a[i]]=1;
        }
    }
    p=n;
    for(i=1;i<=m;i++)
    {
        while(p>q[i].dr)
        {
            if(prec[p]>0)update(1,1,n,prec[p],a[prec[p]]);
            p--;
        }
            ras=0;
            sol=0;
            query(1,1,n,1,dr);
            ras=sol;
            sol=0;
            query(1,1,n,1,st-1);
            ras=ras-sol;
            if(ras<0)ras=ras+666013;
        raspuns[q[i].ind]=ras;
    }
    for(i=1;i<=m;i++)
        printf("%d\n",raspuns[i]);
    return 0;
}