#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
const int MOD=666013;
int aib[N];
int n;

FILE*fin,*fout;

void update(int poz,int val){
  val%=MOD;
  if(poz==0)
    return;
  for(int i=poz;i<=n;i += i&(-i)){
    aib[i]+=val;
    if(aib[i]>=MOD)
      aib[i]-=MOD;
  }
}
int query(int poz){
  int sol=0;
  for(int i=poz;i>0;i -= i&(-i)){
    sol+=aib[i];
    if(sol>=MOD)
      sol-=MOD;
  }
  return sol;

}
int v[N],ap[N];

struct intrebari{
  int st,dr;
  int id;
};
bool cmp(intrebari a,intrebari b){
  return a.dr<b.dr;
}
intrebari qr[N];
int sol[N];
int main()
{
    int k,q;
    fin=fopen("distincte.in","r");
    fout=fopen("distincte.out","w");
    fscanf(fin,"%d%d%d",&n,&k,&q);
    for(int i=1;i<=n;i++)
      fscanf(fin,"%d",&v[i]);
    for(int i=1;i<=q;i++){
      fscanf(fin,"%d%d",&qr[i].st,&qr[i].dr);
      qr[i].id=i;
    }
    sort(qr+1,qr+q+1,cmp);
    int poz=0;
    for(int i=1;i<=q;i++){
      while(poz<qr[i].dr){
        poz++;
        update(poz,v[poz]);
        update(ap[v[poz]],-v[poz]);
        ap[v[poz]]=poz;
      }
      sol[qr[i].id]=(query(poz)-query(qr[i].st)+MOD)%MOD;
    }
    for(int i=1;i<=q;i++)
      fprintf(fout,"%d\n",sol[i]);
    return 0;

}