#include <fstream>
#include <vector>
#define ub(x) (x&(-x))
#define MOD 666013

using namespace std;

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

constexpr int NMAX=1e5 + 5;

int n, k, m;
int a[NMAX];
int ult[NMAX];
int arb[4*NMAX];

vector <pair <int, int> > v[NMAX];

int sol[NMAX];

void update (int nod, int a, int b, int poz, int val)
{
    if (a==b) {
        arb[nod] = (arb[nod] + val) % MOD;
        return;
    }

    int mij=(a+b)/2;

    if (poz <= mij) update(2*nod, a, mij, poz, val);
    else update(2*nod+1, mij+1, b, poz, val);

    arb[nod] = (arb[2*nod] + arb[2*nod+1])%MOD;
}

int query (int nod, int a, int b, int qa, int qb)
{
    if (qa <= a && b <= qb) return arb[nod];

    int mij = (a+b) / 2;
    int r1=0;
    int r2=0;

    if (qa <= mij) r1=query(2*nod, a, mij, qa, qb);
    if (qb > mij)  r2=query(2*nod+1, mij+1, b, qa, qb);

    return (r1+r2)%MOD;
}

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

    for (int i=1; i<=n; ++i)
        f>>a[i];

    for (int i=1; i<=m; ++i)
    {
        int x, y;
        f>>x>>y;
        v[y].push_back({x, i});
    }

    for (int i=1; i<=n; ++i)
    {
        if (ult[a[i]] != 0) update(1, 1, n, ult[a[i]], -a[i]);
        update(1, 1, n, i, a[i]);
        ult[a[i]]=i;

        for (int j=0; j<v[i].size(); ++j)
            sol[v[i][j].second] = query(1, 1, n, v[i][j].first, i);
    }

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