#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
#define PLEC fin.close(); fout.close(); return 0;
using namespace std;
using PII = pair<int, int>;
using QRY = pair<PII, int>;
using VP  = vector<PII>;
using VQ  = vector<QRY>;
using VI  = vector<int>;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
const int mod = 666013;
int aib[110011], n, k, m, j = 1, p;
VI v, last, res;
VQ q;
inline void Update(int poz, int val)
{
    for (int i = poz; i <= n; i += i & -i)
    {
        aib[i] += val;
        if (aib[i] > mod)
            aib[i] -= mod;
    }
}
inline int Query(int poz)
{
    int s = 0;
    for (int i = poz; i > 0; i -= i & -i)
    {
        s += aib[i];
        if (s > mod)
            s -= mod;
    }
    return s;
}
int main()
{
    DAU
    fin >> n >> k >> m;
    v = VI(n + 1);
    last = VI(k + 1);
    res = VI(m + 1);
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    q = VQ(m + 1);
    for (int i = 1; i <= m; ++i)
    {
        fin >> q[i].first.second >> q[i].first.first;
        q[i].second = i;
    }
    sort(q.begin(), q.end());
    for (int i = 1; i <= n; ++i)
    {
        if (last[v[i]])
            Update(last[v[i]], -v[i]);
        last[v[i]] = i;
        Update(i, v[i]);
        p = Query(i);
        while (j <= m && q[j].first.first == i)
            res[q[j].second] = p - Query(q[j].first.second - 1), ++j;
    }
    for (int i = 1; i <= m; ++i)
    {
        if (res[i] < 0)
            res[i] += mod;
        fout << res[i] << '\n';
    }
    PLEC
}