#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

#define MAXM 100005
#define MAXN 100005
#define MOD 666013

int n,k,m;
struct query{int id, st, dr;};
query intrebari[MAXM];
int v[MAXN],rasp[MAXM],aib[MAXN];


bool cmp(query a, query b)
{
    return a.dr < b.dr;
}


void citire()
{
    fin>>n>>k>>m;
    for (int i=1; i<=n; i++)
        fin>>v[i];
    for (int i=1; i<=m; i++)
    {
        fin>>intrebari[i].st>>intrebari[i].dr;
        intrebari[i].id=i;
    }
}



void adauga(int nr, int poz)
{
    for(; poz<=n; poz+=(poz&(-poz)))
        aib[poz] = (aib[poz] + nr + MOD) % MOD;

}

int suma(int poz)
{
    int rasp=0;
    for(; poz>=1; poz-=(poz&(-poz)))
        rasp = (rasp + aib[poz] + MOD) % MOD;
    return rasp;
}


void prelucrare()
{
    sort(intrebari+1, intrebari+m+1, cmp);

    int ultim[MAXN]={0};
    for (int i=1; i<=m; i++)
    {
        for (int j=intrebari[i - 1].dr+1; j<=intrebari[i].dr; j++)
        {
            if (ultim[v[j]]!=0)
                adauga(-v[j],ultim[v[j]]);
            ultim[v[j]]=j;
            adauga(v[j],j);
        }
        rasp[intrebari[i].id] = (suma(intrebari[i].dr) - suma(intrebari[i].st-1) + MOD) % MOD;
    }
}

void afisare()
{
    for (int i=1; i<=m; i++)
        fout<<rasp[i]<<'\n';
}

int main()
{
    citire();
    prelucrare();
    afisare();
    return 0;
}