#include <fstream>
#include <iostream>
#include <vector>
#include <climits>
#include <bits/stdc++.h>
using namespace std;
const int Vmax = 100001;
const int MODUL = 666013;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
struct queries{
int st;
int dr;
int ind;
};
int n, k, m, val[Vmax];
long long sol[Vmax], active[4 * Vmax];
vector<int> lastPos(Vmax, -1);
void build(int nod, int st, int dr){
if(st == dr){
active[nod] = val[st];
return;
}
int mij = (st+dr)/2;
build(2*nod, st, mij);
build(2*nod+1, mij+1, dr);
active[nod] = active[2*nod] + active[2*nod+1];
}
void update(int nod, int st, int dr, int x, int valoare){
if(st==dr){
active[nod] = valoare;
return;
}
int mij = (st+dr)/2;
if(x<=mij)
update(2*nod, st, mij, x, valoare);
else
update(2*nod+1, mij+1, dr, x, valoare);
active[nod] = active[2*nod] + active[2*nod+1];
}
int queryAnswer(int nod, int st, int dr, int x, int y, vector<int> &suma){
if(st == x && dr == y){
return active[nod];
}
int mij = (st+dr)/2;
if(y<=mij)
return queryAnswer(2*nod, st, mij, x, y, suma);
else if(x>mij)
return queryAnswer(2*nod+1, mij+1, dr, x, y, suma);
else
return queryAnswer(2*nod, st, mij, x, mij, suma) + queryAnswer(2*nod+1, mij+1, dr, mij+1, y, suma);
}
int main(){
fin>>n>>k>>m;
vector<queries> query(m, {Vmax, Vmax, Vmax});
for(int i=0;i<n;i++)
fin>>val[i];
for(int j=0;j<m;j++){
fin>>query[j].st;
query[j].st--;
fin>>query[j].dr;
query[j].dr--;
query[j].ind=j;
}
sort(query.begin(), query.end(), [](const queries& a, const queries& b){
return a.dr < b.dr;
});
int j=0;
for(int i=0;i<m;i++){
vector<int> suma;
long long sumaFinala = 0;
while(j<=query[i].dr){
update(1, 0, n-1, j, val[j]);
if(lastPos[val[j]]!=-1){
update(1, 0, n-1, lastPos[val[j]], 0);
}
lastPos[val[j]] = j;
j++;
}
sumaFinala = queryAnswer(1, 0, n-1, query[i].st, query[i].dr, suma);
sol[query[i].ind] = sumaFinala % MODUL;
}
for(int i=0;i<m;i++){
fout<<sol[i]<<'\n';
}
return 0;
}