#include<stdio.h>
#define MAX 100003
#define cst 666013

int a[MAX],urm[MAX],b[MAX],val[MAX];
int st[MAX],dr[MAX],ind[MAX];
int arb[MAX],nb[MAX],sol[MAX];

int comp(int x1,int y1,int x2,int y2)
{
if(y1<y2)
   return -1;
if(y1>y2)
   return 1;
if(x1<x2)
   return -1;
if(x1>x2)
   return 1;
return 0;     
}

void intersc(int &x,int &y)
{
int aux=x;
x=y;
y=aux;     
}

int main()
{
FILE *fin=fopen("distincte.in","r"),
     *fout=fopen("distincte.out","w");
     
int N,i,M,K,j,k;
fscanf(fin,"%d%d%d",&N,&K,&M);
    
for(i=1;i<=N;i++)
  {
  fscanf(fin,"%d",&val[i]);
  a[i]=i;
  }
for(i=1;i<=M;i++)
  {
  fscanf(fin,"%d%d",&st[i],&dr[i]);
  ind[i]=i;
  }
  
for(i=1;i<=K;i++)
  urm[i]=N+1;
  
for(i=N;i;i--)
  {
  b[i]=urm[val[i]];
  urm[val[i]]=i;            
  }
  
//sort 
for(i=1;i<=N;i++)
   {
   j=i;
   while(j/2 && comp(a[j/2],b[j/2],a[j],b[j])<0 )
       {
       intersc(a[j/2],a[j]);
       intersc(b[j/2],b[j]);
       intersc(val[j/2],val[j]);
       j/=2;      
       }
   }
    
i=N;
while(i>1)
 {
 intersc(a[1],a[i]);
 intersc(b[1],b[i]);
 intersc(val[1],val[i]);
 i--;
 
 j=1;
 while(1)
  {
  k=j<<1;
  if(k>i) break;
  if(k+1<=i && comp(a[k+1],b[k+1],a[k],b[k])>0) k++;
  if(comp(a[j],b[j],a[k],b[k])>=0) break;
  
  intersc(a[j],a[k]);
  intersc(b[j],b[k]);
  intersc(val[j],val[k]);
  j=k;
  }         
 }
 
//sort2
for(i=1;i<=M;i++)
  {
  j=i;
  while(j/2 && comp(st[j/2],dr[j/2],st[j],dr[j])<0)
      {
      intersc(st[j/2],st[j]);
      intersc(dr[j/2],dr[j]);
      intersc(ind[j/2],ind[j]);
      j/=2;      
      }      
  }

i=M;
while(i>1)
 {
 intersc(st[1],st[i]);
 intersc(dr[1],dr[i]);
 intersc(ind[1],ind[i]);
 i--;
 
 j=1;
 while(1)
  {
  k=j<<1;
  if(k>i) break;
  if(k+1<=i && comp(st[k],dr[k],st[k+1],dr[k+1])<0) k++;
  if(comp(st[j],dr[j],st[k],dr[k])>=0) break;
  
  intersc(st[j],st[k]);
  intersc(dr[j],dr[k]);
  intersc(ind[j],ind[k]);
  j=k;
  }         
 }
 
nb[0]=0;
for(i=1;i<=N;i++)
   {
   nb[i]=0;
   while( ((1<<nb[i])&i)==0 ) nb[i]++;
   }
    
 
int sol1,sol2;
k=N;
for(i=M;i;i--)
  {
  while(k && b[k]>dr[i])
     {
     j=a[k];     
     while(j<=N)
       {
       arb[j]+=val[k];
       arb[j]%=cst;
       j+=(1<<(nb[j]));       
       }
     k--;
     }
  
  sol1=sol2=0;
  j=dr[i];
  while(j)
    {
    sol2+=arb[j];
    sol2%=cst;
    j-=(1<<(nb[j]));          
    }
    
  j=st[i]-1;
  while(j)
   {
   sol1+=arb[j];
   sol1%=cst;
   j-=(1<<(nb[j]));       
   }  
   
  sol[i]=sol2+cst-sol1;  
  sol[i]%=cst;
  }


//refacere
for(i=1;i<=M;i++)
  {
  j=i;
  while(j/2 && ind[j/2]<ind[j])
    {
    intersc(ind[j/2],ind[j]);
    intersc(sol[j/2],sol[j]);
    j/=2;      
    }               
  }
  
i=M;
while(i>1)
  {
  intersc(ind[1],ind[i]);
  intersc(sol[1],sol[i]);
  i--;
  
  j=1;
  while(1)
   {
   k=j<<1;
   if(k>i) break;
   if(k+1<=i && ind[k+1]>ind[k]) k++;
   if(ind[j] >= ind[k]) break;
   
   intersc(ind[j],ind[k]);
   intersc(sol[j],sol[k]);
   j=k;          
   }
  }
     
for(i=1;i<=M;i++)
   fprintf(fout,"%d\n",sol[i]);
   
fclose(fin);
fclose(fout);
return 0;  
}