#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
const int MOD=666013;
int aint[2*N+N/2];
int lazy[2*N+N/2];
inline void modd(int &x){
  x%=MOD;
}
void updlazy(int nod,int st,int dr){
  if(lazy[nod]){
    aint[nod]+=(1LL*lazy[nod]*(dr-st+1))%MOD;
    modd(aint[nod]);
    if(st!=dr){
      lazy[2*nod]+=lazy[nod];
      modd(lazy[2*nod]);
      lazy[2*nod+1]+=lazy[nod];
      modd(lazy[2*nod+1]);
    }
    lazy[nod]=0;
  }
}
void update(int nod,int st,int dr,int ust,int udr,int val){
  updlazy(nod,st,dr);
  if(st>dr || dr<ust || st>udr)
    return;
  if(st>=ust && dr<=udr){
    aint[nod]+=(1LL*val*(dr-st+1))%MOD;
    modd(aint[nod]);
    if(st!=dr){
      lazy[2*nod]+=lazy[nod];
      modd(lazy[2*nod]);
      lazy[2*nod+1]+=lazy[nod];
      modd(lazy[2*nod]);
    }
    return;
  }
  int mid=(st+dr)/2;
  update(2*nod,st,mid,ust,udr,val);
  update(2*nod+1,mid+1,dr,ust,udr,val);
  aint[nod]=aint[2*nod]+aint[2*nod+1];
  modd(aint[nod]);
}

int query(int nod,int st,int dr,int qst,int qdr){
  updlazy(nod,st,dr);
  if(st>dr || dr<qst || st>qdr)
    return 0;
  if(st>=qst && dr<=qdr)
    return aint[nod];
  int mid=(st+dr)/2;
  return (query(2*nod,st,mid,qst,qdr) + query(2*nod+1,mid+1,dr,qst,qdr))%MOD;
}

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 n,k,q;
    FILE*fin,*fout;
    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(1,1,n,poz,poz,v[poz]);
        update(1,1,n,ap[v[poz]],ap[v[poz]],-v[poz]);
        ap[v[poz]]=poz;
      }
      sol[qr[i].id]=query(1,1,n,qr[i].st,poz);
    }
    for(int i=1;i<=q;i++)
      fprintf(fout,"%d\n",sol[i]);
    return 0;

}