#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];
struct elem
{
    long long x,y,ind;
}Q[100003];
struct elem1
{
    long long s,minim,maxim;
}A[400003];
const long long MOD=666013;
void update(int nod,int st,int dr,int poz,int val)
{
    if(st==dr)
        A[nod]={poz,val,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].s+A[2*nod+1].s,min(A[2*nod].minim,A[2*nod+1].minim),max(A[2*nod].maxim,A[2*nod+1].maxim)};
    }
}
long long query(int nod,int st,int dr,int minim)
{

    long long s=0;
    if(st==dr)
        return st;
    int mid=(st+dr)/2;
    if(A[2*nod].minim>=minim)
        s+=A[2*nod].s;
    else
        if(A[2*nod].maxim>=minim)
            return s+=query(2*nod,st,mid,minim);
    if(A[2*nod+1].minim>=minim)
        s+=A[2*nod+1].s;
    else
        if(A[2*nod+1].maxim>=minim)
            return s+=query(2*nod+1,mid+1,dr,minim);
    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)
        {
            update(1,1,k,V[st],st);
            st++;
        }
        sol[Q[i].ind]=query(1,1,k,Q[i].x)%MOD;
    }
    for(i=1;i<=m;i++)
        fout<<sol[i]<<"\n";
    return 0;
}