#include<stdio.h>
#include<stdlib.h>

int n, k, m, v[100000],f[100000];

int main()
{
  freopen("distincte.in","r",stdin);
  freopen("distincte.out","w",stdout);
  int i, p, u, j;
  long long sum;
  scanf("%d%d%d",&n,&k,&m);
  for (i=1; i<=n; i++) scanf("%d",v+i);
  for (j=1; j<=m; j++)
  {
    scanf("%d%d",&p,&u);
    sum=0;
    for (i=p; i<=u; i++) f[i]=0;
    for (i=p; i<=u; i++)
    {
      if (!f[v[i]])
      {
	sum+=v[i];
	f[v[i]]++;
	sum=sum%666013;
      }
    }
    printf("%lld\n",sum);
  }
  return 0;
}