#include <fstream>
#include <algorithm>

using namespace std;

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

struct str{
    long long l, r, idx;
    bool operator < (const str & aux) const
    {
        if (r != aux.r)
        {
            return r < aux.r;
        }
        return l < aux.l;
    }
};

const int max_size = 1e5 + 1, max_aint = 4e5 + 1, mod = 666013;

long long v[max_size], aint[max_aint], ult[max_size], ans[max_size];
str qr[max_size];

void upd (long long l, long long r, long long poz, long long val, long long nod)
{
    if (l == r)
    {
        aint[nod] += val;
        return;
    }
    long long m = (l + r) / 2;
    if (poz <= m)
    {
        upd(l, m, poz, val, 2 * nod);
    }
    else
    {
        upd(m + 1, r, poz, val, 2 * nod + 1);
    }
    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}

long long query (long long l, long long r, long long st, long long dr, long long nod)
{
    if (st <= l && r <= dr)
    {
        return aint[nod];
    }
    long long m = (l + r) / 2, s1 = 0, s2 = 0;
    if (st <= m)
    {
        s1 = query(l, m, st, dr, 2 * nod);
    }
    if (dr > m)
    {
        s2 = query(m + 1, r, st, dr, 2 * nod + 1);
    }
    return s1 + s2;
}

signed main ()
{
    long long n, k, m;
    in >> n >> k >> m;
    for (long long i = 1; i <= n; i++)
    {
        in >> v[i];
    }
    for (long long i = 1; i <= m; i++)
    {
        in >> qr[i].l >> qr[i].r;
        qr[i].idx = i;
    }
    sort(qr + 1, qr + m + 1);
    long long l = 1;
    for (long long i = 1; i <= n; i++)
    {
        if (ult[v[i]] != 0)
        {
            upd(1, n, ult[v[i]], -v[i], 1);
        }
        upd(1, n, i, v[i], 1);
        ult[v[i]] = i;
        while (l <= m && qr[l].r <= i)
        {
            ans[qr[l].idx] = query(1, n, qr[l].l, qr[l].r, 1) % mod;
            l++;
        }
    }
    for (long long i = 1; i <= m; i++)
    {
        out << ans[i] << '\n';
    }
    in.close();
    out.close();
    return 0;
}