#include<fstream>
#include<algorithm>
#define NMAX 100010
#define NARB 270010
#define MOD 666013

using namespace std;

ifstream f("distincte.in");
ofstream g("distincte.out");

struct query
{
    int st, dr, o, R;
}Q[NMAX];

int n, k, m, sum, a[NMAX], pzp[NMAX], cr[NMAX], arb[NARB];

void Citeste()
{
    int i;

    f>>n>>k>>m;

    for (i=1; i<=n; ++i) f>>a[i];

    for (i=1; i<=m; ++i)
    {
        f>>Q[i].st>>Q[i].dr;
        Q[i].o=i;
    }
}

inline int cmp(query A, query B)
{
    return A.dr<B.dr;
}

void Update(int st, int dr, int pz, int val, int nod)
{
    int mij=(st+dr)/2;

    if (st==dr) arb[nod]=(arb[nod]+val)%MOD;
    else
        if (pz<=mij)
        {
            Update(st, mij, pz, val, 2*nod);
            arb[nod]=(arb[nod]+val)%MOD;
        }
        else
        {
            Update(mij+1, dr, pz, val, 2*nod+1);
            arb[nod]=(arb[nod]+val)%MOD;
        }
    if (arb[nod]<0) arb[nod]+=MOD;
}

void Query(int st, int dr, int x, int y, int nod)
{
    int mij=(st+dr)/2;

    if (x<=st && y>=dr) sum=(sum+arb[nod])%MOD;
    else
    {
        if ( ( st<=x && x<=mij) || ( st<=y && y<=mij) || (x<=st && y>=mij))  Query(st, mij, x, y, nod*2);
        if ( ( mij+1<=x && x<=dr) || ( mij+1<=y && y<=dr) || (x<=mij+1 && y>=dr)) Query(mij+1, dr, x, y, nod*2+1);
    }
}

inline int cmp2(query A, query B)
{
    return A.o<B.o;
}

void Solve()
{
    int  qcr=1, i;

    sort(Q+1, Q+m+1, cmp);

    for (i=1; i<=n; ++i)
    {
        if (pzp[a[i]])
        {
            Update(1, n, pzp[a[i]], -a[i], 1);

            Update(1, n, i, a[i], 1);

            pzp[a[i]]=i;
        }
        else
        {
            Update(1, n, i, a[i], 1);
            pzp[a[i]]=i;
        }

        while (Q[qcr].dr==i)
        {
            sum=0;

            Query(1, n, Q[qcr].st, i, 1);

            Q[qcr].R=sum;

            ++qcr;
        }
    }

    sort(Q+1, Q+m+1, cmp2);
}

void Scrie()
{
    int i;

    for (i=1; i<=m; ++i) g<<Q[i].R<<"\n";
}

int main()
{
    Citeste();

    Solve();

    Scrie();

    f.close();
    g.close();
    return 0;
}