#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, M, K, i, j, v[VAL], P[VAL], nod, A, B;
int poz[VAL], last[VAL], ANS, RASP[VAL], 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;
    int semn=1;
    while (buff[POZ]<'0' || '9'<buff[POZ])
    {
        if (buff[POZ]=='-')
            semn=-1;
        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*semn;
}

int ZERO(int X)
{
    return (X & (-X));
}

void Update(int nod)
{
    while (nod<=N)
    {
        AIB[nod].push_back({last[i], v[i]});
        nod+=ZERO(nod);
    }
}

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

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