#include <fstream>
#include <algorithm>

using namespace std;

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

struct query{
    int x, y, nr;
    long long rez;
};

bool sortq(query a, query b) {
    return a.x < b.x;
}

query a[200001];

int n, m, k;

int v[200001];

long long aib[200001];

void update(int val, int poz) {
    if (poz <= n) {
        aib[poz] += val;
        poz += poz & (-poz);
        update(val, poz);
    }
}

long long q(int poz) {
    if (poz <= 0) {
        return 0;
    } else {
        return aib[poz] + q(poz - (poz & (-poz)));
    }
}

int nxt[200001], nt[200001];

bool fins(query a, query b) {
    return a.nr < b.nr;
}

int main() {
    cin>>n>>k>>m;
    for (int i = 1; i <= n; ++i) {
        cin>>v[i];
    }
    for (int i = n; i >= 1; --i) {
        nxt[i] = nt[v[i]];
        if (nt[v[i]]) {
            update(-v[i], nt[v[i]]);
        }
        nt[v[i]] = i;
        update(v[i], i);
    }
    for (int i = 1; i <= m; ++i) {
        cin>>a[i].x>>a[i].y;
        a[i].nr = i;
    }
    sort(a + 1, a + m + 1, sortq);
    int x = 1;
    for (int i = 1; i <= m; ++i) {
        while (x < a[i].x) {
            update(-v[x], x);
            if (nxt[x]) {
                update(v[x], nxt[x]);
            }
            ++x;
        }
        a[i].rez = q(a[i].y);
    }
    sort(a + 1, a + m + 1, fins);
    for (int i = 1; i <= m; ++i) {
        cout<<a[i].rez % 666013<<"\n";
    }
    return 0;
}