#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, i, a[NMAX], pzp[NMAX], arb[NMAX];

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 ultim(int x)
{
    return x ^ ( x & (x-1) );
}

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

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

int suma(int lim, int pz)
{
    int sum=0;

    for (; pz>lim; pz-=ultim(pz)) sum=(sum+arb[pz])%MOD;

    return sum;
}

void Update(int pz, int val)
{
    for (; pz<=i; pz+=ultim(pz))
        arb[pz]+=val;
}

void Solve()
{
    int  qcr=1;

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

    for (i=1; i<=n; ++i)
    {
        if (pzp[a[i]])
        {
            arb[i]=(a[i]+suma(i-ultim(i), i-1))%MOD;

            Update(pzp[a[i]], -a[i]);

            pzp[a[i]]=i;
        }
        else
        {
            arb[i]=(a[i]+suma(i-ultim(i), i-1))%MOD;

            pzp[a[i]]=i;
        }

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

            Q[qcr].R=suma(0, i)-suma(0, Q[qcr].st-1);

            if (Q[qcr].R<0) Q[qcr].R+=MOD;

            ++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;
}