#include <fstream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define F first
#define S second

using namespace std;

const int VAL=100005;
const int MOD=666013;

int N, v, P[VAL], nod, A, B;
int poz[VAL], last[VAL], ANS, X;
vector < pair <int, int> > AIB[VAL];
pair < pair <int, int>, int > Q[VAL];

char buff[VAL];
int POZ=0;

int citeste()
{
    int nr=0;
    while (buff[POZ]<'0' || '9'<buff[POZ])
        if (++POZ==VAL)
            fread(buff, 1, VAL, stdin), POZ=0;
    while ('0'<=buff[POZ] && buff[POZ]<='9')
    {
        nr=nr*10+buff[POZ]-'0';
        if (++POZ==VAL)
            fread(buff, 1, VAL, stdin), POZ=0;
    }
    return nr;
}

void Update()
{
    while (nod<=N)
    {
        AIB[nod].push_back({A, B});
        nod+=(nod & (-nod));
    }
}

void Query()
{
    while (nod>0)
    {
        while (1)
        {
            if (P[nod]+1==AIB[nod].size() || AIB[nod][P[nod]+1].F>=A)
                break;
            P[nod]++;
        }
        if (P[nod]>=0)
        {
            ANS+=X*AIB[nod][P[nod]].S;
            if (ANS>=MOD)
                ANS-=MOD;
            if (ANS<0)
                ANS+=MOD;
        }
        nod-=(nod & (-nod));
    }
}

int main()
{
    int RASP[VAL], M, K, j, i;
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
    N=citeste();
    K=citeste();
    M=citeste();
    for (i=1; i<=N; i++)
    {
        v=citeste();
        last[i]=poz[v];
        poz[v]=i;
        A=last[i];
        B=v;
        nod=i;
        Update();
    }
    for (i=1; i<=N; i++)
    {
        P[i]=-1;
        nod=i;
        sort(AIB[nod].begin(), AIB[nod].end());
        for (j=1; j<AIB[nod].size(); j++)
        {
            AIB[nod][j].S+=AIB[nod][j-1].S;
            if (AIB[nod][j].S>=MOD)
                AIB[nod][j].S-=MOD;
        }
    }
    for (i=1; i<=M; i++)
    {
        Q[i].F.F=citeste();
        Q[i].F.S=citeste();
        Q[i].S=i;
    }
    sort(Q+1, Q+M+1);
    for (i=1; i<=M; i++)
    {
        ANS=0;
        A=Q[i].F.F;
        B=Q[i].F.S;
        X=1;
        nod=B;
        Query();
        X=-1;
        nod=A-1;
        Query();
        RASP[Q[i].S]=ANS;
    }
    for (i=1; i<=M; i++)
        printf("%d\n", RASP[i]);
    return 0;
}