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

FILE*fin,*fout;

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

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

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

}