#include <fstream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

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

int N, M, K, i, j, v[VAL], P, nod;
int poz[VAL], last[VAL], ANS, A, B;
vector < pair <int, int> > AIB[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);
    }
}

int Binary_Search(int nod, int X)
{
    int be=0, en=AIB[nod].size()-1;
    int mid, P=-1;
    while (be<=en)
    {
        mid=(be+en) / 2;
        if (AIB[nod][mid].first<X)
        {
            P=mid;
            be=mid+1;
        }
        else
            en=mid-1;
    }
    return P;
}

void Query(int nod, int X)
{
    while (nod>0)
    {
        P=Binary_Search(nod, A);
        if (P>=0)
        {
            ANS+=X*AIB[nod][P].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++)
    {
        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;
        }
    }
    while (M>0)
    {
        M--;
        A=citeste();
        B=citeste();
        ANS=0;
        Query(B, 1);
        Query(A-1, -1);
        printf("%d\n", ANS);
    }
    return 0;
}