#include <fstream>
#include <algorithm>
#define N 100010
#define M 666013

using namespace std;

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

int n,i,j,V[N],P[N],k,m,AIB[N],ANS[N];

struct query
{
    int x,y,p;
} Q[N];

bool CompQ (query a, query b)
{
    return a.y<b.y;
}

void Update (int p, int v)
{
    if (!p) return;
    for (;p<=n;p+=p&(-p))
    {
        AIB[p]=(AIB[p]+v)%M;
        if (AIB[p]<0) AIB[p]+=M;
    }
}

int Query (int p)
{
    int v=0;
    for (;p>=1;p-=p&(-p))
        v=(v+AIB[p])%M;
    return v;
}

int main ()
{
    f >> n >> k >> m;
    for (i=1;i<=n;i++)
        f >> V[i];
    for (i=1;i<=m;i++)
    {
        f >> Q[i].x >> Q[i].y;
        Q[i].p=i;
    }

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

    for (i=1;i<=m;i++)
    {
        for (j=Q[i-1].y+1;j<=Q[i].y;j++)
        {
            Update(P[V[j]],-V[j]);
            Update(j,V[j]);
            P[V[j]]=j;
        }
        ANS[Q[i].p]=Query(Q[i].y)-Query(Q[i].x-1);
        if (ANS[Q[i].p]<0) ANS[Q[i].p]+=M;
    }

    for (i=1;i<=m;i++)
        g << ANS[i] << '\n';
    f.close();g.close();
    return 0;
}