#include<algorithm>
#include<cstdio>
#define mod 666013
#define NMax 100005
using namespace std;

struct cv { int x,y,ord; };
cv qr[NMax];
int aib[NMax],poz[NMax],n;
int a[NMax],sol[NMax];

bool cmp (cv aa, cv bb)
{
    return aa.y<bb.y;
}

void update (int poz, int val)
{
    while (poz<=n)
    {
        aib[poz]+=val;
        if (aib[poz]>=mod)
            aib[poz]-=mod;
        poz+=poz&(-poz);
    }
}

int query (int poz)
{
    int sum=0;
    while (poz>0)
    {
        sum+=aib[poz];
        if (sum>=mod)
            sum-=mod;
        poz-=poz&(-poz);
    }
    return sum;
}

int main ()
{
    int i,j,k,m;
    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<=m; i++)
    {
        scanf("%d%d",&qr[i].x,&qr[i].y);
        qr[i].ord=i;
    }
    sort(qr+1,qr+m+1,cmp);
    for (i=1; i<=m; i++)
    {
        for (j=qr[i-1].y+1; j<=qr[i].y; j++)
        {
            if (poz[a[j]])
                update(poz[a[j]],-a[j]);
            update(j,a[j]);
            poz[a[j]]=j;
        }
        sol[qr[i].ord]=(query(qr[i].y)-query(qr[i].x-1))%mod;
    }
    for (i=1; i<=m; i++)
        printf("%d\n",sol[i]);
    return 0;
}