#include <bits/stdc++.h>
#define NMAX 100001
#define MOD 666013
using namespace std;

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

int v[NMAX]; ///vectorul citit
int ult_poz[NMAX]; ///pentru fiecare valoare salvam ultima sa aparitie
int aib[NMAX]; ///daca al i-lea element este ultima aparitie a valorii, atunci il adunam

void update(int poz, int val, int n) ///update aib
{
    while(poz<=n)
    {
        aib[poz]+=val;
        if(aib[poz]>=MOD) aib[poz]-=MOD;
        poz+=(poz&(-poz));
    }
}

int query(int poz) ///query aib
{
    int suma=0;
    while(poz>0)
    {
        suma+=aib[poz];
        if(suma>=MOD) suma-=MOD;
        poz-=(poz&(-poz));
    }
    return suma;
}

struct interval{int poz=0, st=0, dr=0;};
bool cmp(interval a, interval b) {return (a.dr<b.dr);}
interval intervale[NMAX]; ///intervalele citite
int ans[NMAX];

int main()
{
    int n, k, m;
    in >> n >> k >> m;
    for(int i=1; i<=n; i++)
    {
        in >> v[i];
    }
    for(int i=1; i<=m; i++)
    {
        in >> intervale[i].st >> intervale[i].dr;
        intervale[i].poz=i;
    }
    sort(intervale+1, intervale+m+1, cmp); ///sortam intervalele dupa capatul dreapta
    int j=1;
    for(int i=1; i<=n; i++)
    {
        if(ult_poz[v[i]]!=0)
        {
            update(ult_poz[v[i]], MOD-v[i], n); ///ult_poz[v[n]] nu mai este ultima aparitie a valorii v[n]
        }
        update(i, v[i], n);
        ult_poz[v[i]]=i;

        while(i==intervale[j].dr)
        {
            ans[intervale[j].poz]=(query(intervale[j].dr)-query(intervale[j].st-1)+MOD)%MOD;
            j++;
        }
    }
    for(int i=1; i<=m; i++) ///afisam raspunsul pentru fiecare interval
    {
        out << ans[i] << "\n";
    }

    return 0;
}