#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5 + 7, MOD = 666013;

typedef pair < int, int > pii;

vector < pii > qry[N];///first = right; second = indicele qryului

int lastfrq[N];
int urm[N], sufsm[N], raspuns[N], v[N];

namespace AIB {
    int t[N];

    void Update(int poz, int val) {
        for (; poz > 0; poz -= (poz&(-poz)))
            t[poz] += val, t[poz] -= (t[poz] >= MOD ? MOD : 0);
    }

    int Query(int poz) {
        int ans(0);
        while (poz < N) {
            ans += t[poz];
            if (ans >= MOD)
                ans -= MOD;
            poz += (poz&(-poz));
        }
        return ans;
    }
}

int main()
{
    int n, k, m, a, b;
    fin >> n >> k >> m;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    for (int i = 1; i <= m; ++i)
        fin >> a >> b, qry[a].push_back({b, i});
    for (int i = n; i >= 1; --i) {
        if (lastfrq[v[i]] == 0)
            urm[i] = n + 1;
        else
            urm[i] = lastfrq[v[i]];
        lastfrq[v[i]] = i;
        sufsm[i] = sufsm[i + 1] + v[i];
        if (sufsm[i] >= MOD)
            sufsm[i] -= MOD;
    }
    for (int i = n; i >= 1; --i) {
        AIB::Update(urm[i], v[i]);
        ///OBS : cand dam query pt un dreapta o sa le insumeze pe toate alea bune + toate alea care sunt dupa dreapta deci da scad sufsm[dr + 1] o sa dea bine
        for (auto qr : qry[i]) {
            raspuns[qr.second] = AIB::Query(qr.first + 1) - sufsm[qr.first + 1];
            if (raspuns[qr.second] < 0)
                raspuns[qr.second] += MOD;
        }
    }
    for (int i = 1; i <= m; ++i)
        fout << raspuns[i] << '\n';
    return 0;
}