#include <stdio.h>
using namespace std;
struct lista
{
 long inf;
 lista *urm;
};
long n,m,k;
lista *c[100001];
int main()
{
 freopen("distincte.in","r",stdin);
 freopen("distincte.out","w",stdout);
 scanf("%ld %ld %ld\n",&n,&k,&m);
 lista *q;
 long i,x,j;
 for (i=1;i<=n;i++)
 {
  scanf("%ld\n",&x);
  q=new lista;
  q->inf=i;
  q->urm=c[x];
  c[x]=q;
 }
 long y,s;
 for (i=0;i<m;i++)
 {
  s=0;
  scanf("%ld %ld\n",&x,&y);
  for (j=1;j<=k;j++)
  {
   q=c[j];
   while (q&&q->inf>y)
    q=q->urm;
   if (q&&q->inf<=y&&q->inf>=x)
   {
    s+=j;
    s%=666013;
   }
  }
  printf("%ld\n",s);
 }
 return 0;
}