#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxn 100010
#define maxx 262144
#define mod 666013

int n,k,m,l,px,py,v;
int a[maxn],b[maxn],c[maxn];
int x[maxn],y[maxn],p[maxn],sol[maxn];
int s[maxx];

int cmp(int i,int j)
{
    return (y[i]<y[j]);
}

void update(int p,int r,int nod)
{
     if ((px<=p) && (r<=py)) s[nod]=v;
     else {
              int q=(p+r)/2;
              
              if (px<=q) update(p,q,nod*2);
              if (py>q) update(q+1,r,nod*2+1);
              
              s[nod]=s[nod*2]+s[nod*2+1];
              if (s[nod]>=mod) s[nod]-=mod;
          }
}

int query(int p,int r,int nod)
{
    if ((px<=p) && (r<=py)) return s[nod];
    else {
             int q=(p+r)/2,rez=0;
             if (px<=q) rez+=query(p,q,nod*2);
             if (py>q) rez+=query(q+1,r,nod*2+1);
             if (rez>=mod) rez-=mod;
             return rez;
         }
}

int main()
{
    freopen("distincte.in","r",stdin);
    freopen("distincte.out","w",stdout);
    
    int i,j;
    scanf("%d %d %d",&n,&k,&m);
    
    for (i=1;i<=n;i++) 
    {
        scanf("%d ",&a[i]);
        b[i]=c[a[i]];
        c[a[i]]=i;
    }
    
    for (i=1;i<=m;i++) 
    {
        scanf("%d %d",&x[i],&y[i]);
        p[i]=i;
    }
    
    sort(p+1,p+m+1,cmp);
    
    for (l=1;l<=n;l<<=1);
    
    j=1;
        
    for (i=1;i<=n;i++)
    {
        if (b[i]!=0) 
        {
             px=b[i];
             py=b[i];        
             v=0;
             update(1,l,1);
        }
                
        px=i;
        py=i;
        v=a[i];
        update(1,l,1);
                        
        while ((j<=m) && (y[p[j]]==i))
        {
            px=x[p[j]];
            py=y[p[j]];
            sol[p[j]]=query(1,l,1); 
            j++;
        }
    }
        
    for (i=1;i<=m;i++) printf("%d\n",sol[i]);
        
    return 0;
}