#include <iostream>
#include <fstream>
#include <algorithm>
#define MOD 666013

using namespace std;

int pred[100010];
int v[100010];
int aib[100010];
int sol[100010];
int n, m, k;

struct intrebare
{
    int st, dr, ind;
};
intrebare q[100010];

inline void Read()
{
    ifstream f ("distincte.in");
    f>>n>>k>>m;
    int i;
    for (i=1; i<=n; i++)
        f>>v[i];
    for (i=1; i<=m; i++)
    {
        f>>q[i].st>>q[i].dr;
        q[i].ind = i;
    }
    f.close();
}

inline bool cmp (const intrebare A, const intrebare B)
{
    if (A.dr == B.dr)
        return A.st < B.st;
    return A.dr < B.dr;
}

inline void Update(int poz, int x)
{
    if (poz == 0)
        return;
    while (poz <= n)
    {
        aib[poz] += x;
        aib[poz] %= MOD;
        if (aib[poz] < 0)
            aib[poz]+=MOD;
        poz += (poz & (-poz));
    }
}

inline int Query(int poz)
{
    int s = 0;
    while (poz > 0)
    {
        s += aib[poz];
        s %= MOD;
        poz -= (poz & (-poz));
    }
    return s;
}

inline void Solve()
{
    /**
        pred[i] = cea mai din dreapta pozitie din stanga din v
        la care se afla numarul i la un anumit pas
        cu variabila poz parcurg vectorul v
    */
    int i, poz, rez;
    sort(q+1, q+m+1, cmp);
    poz = 0;
    for (i=1; i<=m; i++)
    {
        while (poz < q[i].dr)
        {
            poz++;
            Update(pred[v[poz]], -v[poz]); /// sterg numarul v[poz] de la vechea pozitie in care se afla
            Update(poz, v[poz]); /// adaug v[poz] la noua pozitie poz la care se afla
            pred[v[poz]] = poz; /// actualizez pred
        }
        rez = Query(q[i].dr) - Query(q[i].st-1);
        if (rez < 0)
            rez += MOD;
        sol[q[i].ind] = rez;
    }
}

inline void Write()
{
    ofstream g("distincte.out");
    int i;
    for (i=1; i<=m; i++)
        g<<sol[i]<<"\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}