#include <fstream>
#include <algorithm>

const int Nmax = 100010;
const int Mod = 666013;

using namespace std;

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

int N,K,M;
int V[Nmax],P[Nmax];
int AIB[Nmax],ANS[Nmax];

struct query { int x,y,p; } Q[Nmax];
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)%Mod;
        if (AIB[p]<0) AIB[p]+=Mod;
    }
}

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

int main ()
{
    f >> N >> K >> M;
    for (int i=1;i<=N;i++)
        f >> V[i];
    for (int i=1;i<=M;i++)
    {
        f >> Q[i].x >> Q[i].y;
        Q[i].p=i;
    }

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

    for (int i=1;i<=M;i++)
    {
        for (int 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]+=Mod;
    }

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