#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 100000;
const int MODULO = 666013;
const int KMAX = 100000;

struct Query
{
    int index;
    int st;
    int dr;

    Query() = default;

    Query(int index, int st, int dr):
        index(index), st(st), dr(dr) {};

    bool operator <(const Query& other) const
    {
        return this->st < other.st;
    }
};

vector<Query> queries;

long long sol[1 + NMAX];

int v[1 + NMAX];
int aparitie[1 + KMAX];

long long aint[1 + 4 * NMAX];

vector<int> aparitii[1 + KMAX];

long long queryAint(int index, int st, int dr, int stQ, int drQ)
{
    if (st == stQ && drQ == dr)
        return aint[index];

    int mij = (st + dr) / 2;

    int fiuSt = 2 * index;
    int fiuDr = 2 * index + 1;

    if (drQ <= mij)
        return queryAint(fiuSt, st, mij, stQ, drQ);
    else if (stQ >= mij + 1)
        return queryAint(fiuDr, mij + 1, dr, stQ, drQ);
    else
        return queryAint(fiuSt, st, mij, stQ, mij) + queryAint(fiuDr, mij + 1, dr, mij + 1, drQ);
}

void updateAint(int index, int st, int dr, int poz, int val)
{
    if (st == dr)
    {
        aint[index] = val;
        return;
    }

    int mij = (st + dr) / 2;

    int fiuSt = 2 * index;
    int fiuDr = 2 * index + 1;

    if (poz <= mij)
        updateAint(fiuSt, st, mij, poz, val);
    else
        updateAint(fiuDr, mij + 1, dr, poz, val);

    aint[index] = aint[fiuSt] + aint[fiuDr];
}

int main()
{
    ios_base::sync_with_stdio(false);

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

    int n, k, m;
    in >> n >> k >> m;

    for (int i = 1; i <= n; i++)
        in >> v[i];

    for (int i = n; i >= 1; i--)
        aparitii[v[i]].emplace_back(i);

    for (int i = 1; i <= n; i++)
        updateAint(1, 1, n, aparitii[v[i]].back(), v[i]);

    for (int i = 1; i <= m; i++)
    {
        int st, dr;
        in >> st >> dr;

        queries.emplace_back(i, st, dr);
    }

    sort(queries.begin(), queries.end());

    int stQuery = 1;

    for (int i = 0; i < queries.size(); i++)
    {
        while (stQuery < queries[i].st)
        {
            updateAint(1, 1, n, stQuery, 0);

            aparitii[v[stQuery]].pop_back();

            updateAint(1, 1, n, aparitii[v[stQuery]].back(), v[stQuery]);

            stQuery++;
        }

        sol[queries[i].index] = queryAint(1, 1, n, queries[i].st, queries[i].dr);
    }

    for (int i = 1; i <= m; i++)
        out << sol[i] % MODULO << '\n';

    in.close();
    out.close();

    return 0;
}