#include <fstream>
#include <algorithm>
using namespace std;

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

const int MAXM = 100005;
const int MAXN = 100005;
const int MODULO = 666013;

int n,k,m;

struct intrebare
{
    int id, st, dr;
};

bool ordine_buna(intrebare a, intrebare b)
{
    if (a.dr < b.dr)
        return true;
    if (a.dr > b.dr)
        return false;
    return a.st < b.st;
}

intrebare intrebari[MAXM];

int v[MAXN];

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

int rasp[MAXM];

int aib[MAXN];

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

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

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

    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) + MODULO) % MODULO;
    }
}

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

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