#include<fstream>
#include<algorithm>
#define MOD 666013
using namespace std;
ifstream fi("distincte.in");
ofstream fo("distincte.out");
typedef struct qrry{int x,y,ind;} QRRY;
QRRY Q[100001];
int n,k,m,i,ind,Next[100001],P[100001],X[100001],F[100001],Rez[100001];

bool cmp(QRRY a, QRRY b)
{
    return a.x>b.x;
}

void update(int val, int poz)
{
    while(poz<=n)
    {
        F[poz]=(F[poz]+val+MOD)%MOD;
        poz=poz+(poz^(poz&(poz-1)));
    }
}

int f(int poz)
{
    int rez=0;
    while(poz>=1)
    {
        rez=(rez+F[poz]+MOD)%MOD;
        poz=poz-(poz^(poz&(poz-1)));
    }
    return rez%MOD;
}

int querry(int st, int dr)
{
    return (f(dr)-f(st-1)+MOD)%MOD;
}

int main()
{
    fi>>n>>k>>m;
    for(i=1; i<=n; i++)
    {
        fi>>X[i];
        update(X[i],i);
        Next[P[X[i]]]=i;
        P[X[i]]=i;
    }
    for(i=1; i<=n; i++)
    {
        if(Next[i]==0)
            Next[i]=n+1;
    }
    for(i=1; i<=m; i++)
    {
        fi>>Q[i].x>>Q[i].y;
        Q[i].ind=i;
    }
    sort(Q+1,Q+n+1,cmp);
    ind=n;
    for(i=1; i<=m; i++)
    {
        while(ind>=1 && ind>=Q[i].x)
        {
            //elimin celelalte aparitii ale lui X[ind]
            update(-X[ind],Next[ind]);
            ind--;
        }
        Rez[Q[i].ind]=querry(Q[i].x,Q[i].y);
    }
    for(i=1; i<=m; i++)
        fo<<Rez[i]<<"\n";
    fi.close();
    fo.close();
    return 0;
}