#include <fstream>
#include <vector>
#define LL long long

using namespace std;

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

const int N = 100005;
vector <pair<int,int> > qr[N];
vector <pair<int,int> >::iterator w;
int n, k, m, i, j, a[N], last[N], x, y;
LL sol[N], arb[N];

void add(int poz, int val) {
    for (;poz <= n; poz += poz&-poz)
        arb[poz] += val;
}

LL sum(int poz) {
    LL suma = 0;
    for (;poz > 0; poz -= poz&-poz)
        suma += arb[poz];
    return suma;
}

int main() {
    f >> n >> k >> m;
    for (i = 1; i <= n; i++)
        f >> a[i];

    for (i = 1; i <= m; i++) {
        f >> x >> y;
        qr[y].push_back({x, i});
    }

    for (i = 1; i <= n; i++) {
        if (last[ a[i] ]) add(last[ a[i] ], -a[i]);
        last[ a[i] ] = i;
        add(i, a[i]);
        for (w = qr[i].begin(); w != qr[i].end(); w++)
            sol[w -> second] = sum(i) - sum(w -> first - 1);
    }

    for (i = 1; i <= m; i++)
        g << sol[i]%666013 << '\n';
}