#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("distincte.in");
ofstream fout("distincte.out");
long long n,m,k,i,st,V[100003],sol[100003],A[400003],f[100003];
struct elem
{
long long x,y,ind;
}Q[100003];
const long long MOD=666013;
void update(int nod,int st,int dr,int poz,int val)
{
if(st==dr)
A[nod]=val;
else
{
int mid=(st+dr)/2;
if(poz<=mid)
update(2*nod,st,mid,poz,val);
else
update(2*nod+1,mid+1,dr,poz,val);
A[nod]=(A[2*nod]%MOD+A[2*nod+1]%MOD)%MOD;
}
}
long long query(int nod,int st,int dr,int a,int b)
{
if(a<=st&&dr<=b)
return A[nod];
else
{
long long s=0;
int mid=(st+dr)/2;
if(a<=mid)
s+=query(2*nod,st,mid,a,b);
s%=MOD;
if(mid+1<=b)
s+=query(2*nod+1,mid+1,dr,a,b);
s%=MOD;
return s;
}
}
int main()
{
fin>>n>>k>>m;
for(i=1;i<=n;i++)
fin>>V[i];
for(i=1;i<=m;i++)
{
fin>>Q[i].x>>Q[i].y;
Q[i].ind=i;
}
sort(Q+1,Q+m+1,[](elem a,elem b){return a.y<b.y;});
st=1;
for(i=1;i<=m;i++)
{
while(st<=Q[i].y)
{
if(f[V[st]])
update(1,1,n,f[V[st]],0);
update(1,1,n,st,V[st]);
f[V[st]]=st;
st++;
}
sol[Q[i].ind]=query(1,1,n,Q[i].x,Q[i].y)%MOD;
}
for(i=1;i<=m;i++)
fout<<sol[i]%MOD<<"\n";
return 0;
}