#include <bits/stdc++.h>
#define mod 666013
#define ind(x) (x&(-x))

using namespace std;

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

int n;
long long aib[100100];

struct distincte
{
    int st,dr,indice;
}v[100100];

int compare(distincte A,distincte B)
{
    if(A.dr==B.dr) return (A.st<B.st);
    return (A.dr<B.dr);
}

void update(int pos,int val)
{
    int i;
    for(i=pos;i<=n;i+=ind(i))
        aib[i]+=val;
}

long long suma(int pos)
{
    int i;
    long long S=0;
    for(i=pos;i>=1;i-=ind(i))
        S+=aib[i];
    return S;
}


int k,Q,i,interval,j,m,poz,identic[100100],a[100100];
long long sol[100100];

int main()
{
    f>>n>>k>>m;

    for(i=1;i<=n;i++)
    {
        f>>a[i];
        update(i,a[i]); // le pun in aib
    }

    for(i=1;i<=m;i++)
    {
        f>>v[i].st>>v[i].dr;
        v[i].indice=i;
    }

    sort(v+1,v+m+1,compare); // sortez intervalele (st;dr) dupa indicele lui dr, iar apoi dupa indicele lui st (in caz de "=" la dr)

    // identic[v[i]] = cea mai din dreapta pozitie care il are pe v[i]

    poz=1;
    for(interval=1;interval<=m;interval++)
    {
        for(j=poz;j<=v[interval].dr;j++) // parcurgem de la indicele de unde s-a terminat intervalul anterior (unde am ramas la pasul anterior), pana la indicele unde se termina intervalul actual => in final, tot m pasi o sa fac
        {
            if(identic[a[j]]!=0) // daca a mai aparut in urma
            {
                update(identic[a[j]],-a[j]); // ii dau update in vecotrul meu si il fac 0. il fac 0 pentru ca aparitia lui anterioara (de pe pozitia identic[a[j]]) nu mai afecteaza intervalul curent, implicit nici pe cele urmatoare (acestea fiind sortate dupa capatul dr)
                                             // iar update ii dau prin operatia de AIB. scad valoarea a[j] pe pozitia identic[a[j]] => ca pe pozitia aceea dupa update o sa fie 0
                identic[a[j]]=j;
            }
            else
            {
                identic[a[j]]=j;
            }
        }

        poz=v[interval].dr+1; // dam update la poz

        // acum pentru intervalul meu, pot sa calculez sume "partiale". S1 = suma pana la capatul dr. S2 = suma pana la capatul (st-1) => rezultatul o sa fie S2-S1
        // solutia garanteaza ca nu se repeta numere in aceste sume, pentru ca am facut smecheria cu vectorul "identic" ( in care daca la pasul j, elementul a[j] mai aprea o data in spate, il faceam pe cel din spate = 0, schimbare care nu mai afecta in continuare restul intervalelor)

        sol[v[interval].indice]=suma(v[interval].dr)-suma(v[interval].st-1);
    }

    for(i=1;i<=m;i++)
        g<<sol[i]%mod<<'\n';
    return 0;
}