#include <bits/stdc++.h>
#define ub(x) x&(-x)

using namespace std;

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

struct queryy
{
    int st, dr, idx;

    bool operator< (const queryy& other) const
    {
        return dr < other.dr;
    }
};

const int nmax = 1e5 + 5;
const int mod = 666013;

int n, k, q, v[nmax], aib[nmax], ult[nmax], sol[nmax];

queryy qy[nmax];

void update (int poz, int val)
{
    for (int i = poz; i <= n; i += ub (i))
        aib[i] = (aib[i] + val + mod) % mod;
}

int query (int poz)
{
    int s = 0;
    for (int i = poz; i >= 1; i -= ub (i))
        s = (s + aib[i]) % mod;
    return s;
}

signed main ()
{
    fin >> n >> k >> q;
    for (int i = 1; i <= n; i++)
        fin >> v[i];
    for (int i = 1; i <= q; i++)
    {
        fin >> qy[i].st >> qy[i].dr;
        qy[i].idx = i;
    }
    sort (qy + 1, qy + 1 + q);
    int i = 1;
    for (int t = 1; t <= q; t++)
    {
        int j = qy[t].dr;
        while (i <= j)
        {
            if (ult[v[i]])
                update (ult[v[i]], -v[i]);
            update (i, v[i]);
            ult[v[i]] = i;
            i++;
        }
        sol[qy[t].idx] = query (qy[t].dr) - query (qy[t].st - 1);
    }
    for (int i = 1; i <= q; i++)
        fout << sol[i] << "\n";
    return 0;
}