#include <bits/stdc++.h>
#define mod 666013
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
int n,m,k,last[100005];
int a[100005],ans[100005];
int arb[500005];
struct qr
{
   int x,y,ord;
};
qr b[100005];

bool cmp( qr h, qr j)
{
        return h.y<j.y;
}


void update(int nod,int l,int r,int pz,int val)
{
    if(l==pz && pz==r)
    { arb[nod]=val;
    if(arb[nod]>mod)
        arb[nod]-=mod;
    return;
    }
    int mid=(l+r)/2;

    if(pz>mid)
        update(2*nod+1,mid+1,r,pz,val);
    else update(2*nod,l,mid,pz,val);
   arb[nod]=arb[nod*2]+arb[2*nod+1];
   if(arb[nod]>mod)
    arb[nod]-=mod;
}

long long query(int nod,int l,int r,int st,int dr)
{
    if(l==st && r==dr)
        return arb[nod];

    int mid=(l+r)/2;

    if(st>mid)
        return query(2*nod+1,mid+1,r,st,dr);
    else if(dr<=mid)
         return query(2*nod,l,mid,st,dr);
    else
    {  int h=query( 2*nod,l,mid,st,mid)+query(2*nod+1,mid+1,r,mid+1,dr);
      if(h>mod) h-=mod;
     return h;
    }
}

int main()
{
    fin>>n>>k>>m;
    int i,j;
    for(i=1;i<=n;++i) fin>>a[i];
    for(i=1;i<=m;++i)
    { fin>>b[i].x>>b[i].y;
       b[i].ord=i;
    }
    sort(b+1,b+m+1,cmp);
    j=1;
    for(i=1;i<=n;++i)
    {
        if(last[a[i]]) update(1,1,n,last[a[i]],0);
        update(1,1,n,i,a[i]);

        while( j<=m && b[j].y==i)
        {
            ans[  b[j].ord ]=query(1,1,n,b[j].x,b[j].y);
            ++j;
        }

        last[a[i]]=i;
    }
    for(i=1;i<=m;++i)
        fout<<ans[i]<<"\n";
    return 0;
}