#include <fstream>
#include <algorithm>
#define zeros(x) ((x^(x-1))&x)

using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
struct intr{int x,y,z;};
intr v[100001];
int a[100001],aib[100001],mod=666013,u[100001],n,k,m,i,j,ras[100001];
bool cmp(intr a,intr b)
{
  return (a.y<b.y);
}
void update(int poz,int val)
{
  int j=0;
  for (j=poz;j<=n;j+=zeros(j))
  aib[j]+=val,aib[j]%=mod;
}
int query(int poz)
{
  int j=0,sum=0;
  for (j=poz;j>=1;j-=zeros(j))
    sum+=aib[j],sum%=mod;
  return sum;
}
int main()
{
    f>>n>>k>>m;
    for (i=1;i<=n;i++)
      f>>a[i],u[a[i]]=n+1;

    for (i=1;i<=m;i++)
    {
      f>>v[i].x>>v[i].y;
      v[i].z=i;
    }
    j=1;
    sort(v+1,v+m+1,cmp);
    for (i=1;i<=m;i++)
    {
     while(j<=v[i].y)
       update(u[a[j]],-a[j]),update(j,a[j]),u[a[j]]=j,j++;
     ras[v[i].z]=query(v[i].y)-query(v[i].x-1);
     ras[v[i].z]%=mod;
    }
    for (i=1;i<=m;i++)
      g<<ras[i]<<'\n';
    return 0;
}