#include <stdio.h>
#include <string.h>

#define Nmax 100000
#define MOD 666013

int n,k,m,i,st,dr,v[Nmax],h[Nmax];

int Mod(int x)
{
   while (x>=MOD) x-=MOD;
   return x;
}

int main()
{
   freopen("distincte.in","r",stdin);
   scanf("%d %d %d",&n,&k,&m);
   for (i=0;i<n;i++) scanf("%d",&v[i]);

   freopen("distincte.out","w",stdout);
   memset(h,0,sizeof(h));
   for (int test=1;test<=m;test++)
      {
         scanf("%d %d",&st,&dr);
         st--; dr--;
         int sum=0;
         for (i=st;i<=dr;i++)
            if (h[v[i]]!=test)
              {
                 h[v[i]]=test;
                 sum=Mod(sum+v[i]);
              }
         printf("%d\n",sum);
      }
   fclose(stdout);
   return 0;
}