#include <bits/stdc++.h>
#define MN 107171
typedef long long ll;
using namespace std;

namespace AIB {
    ll V[MN];
    void up(ll p, ll v) {
        if(!p) return;
        while(p < MN) V[p] += v, p += p & (-p);
    }
    ll f(ll p) {
        ll r = 0;
        while(p) r += V[p], p -= p & (-p);
        return r;
    }
    ll query(ll st, ll dr) {
        return f(dr) - (st ? f(st-1) : 0);
    }
}
ll n, k, m, V[MN], L[MN];
ifstream fi("distincte.in");
ofstream fo("distincte.out");
tuple<ll, ll, ll> Q[MN];
ll UnL[MN], R[MN];
int main() {
    fi >> n >> k >> m;
    for(ll i = 1; i <= n; ++i) {
        fi >> V[i];
        UnL[i] = L[V[i]];
        L[V[i]] = i;
    }
    for(ll i = 1, a, b; i <= m; ++i)
        fi >> a >> b, Q[i] = {a, b, i};
    sort(Q + 1, Q + n + 1, [&](auto a, auto b) {
         if(get<1>(a) != get<1>(b)) return get<1>(a) > get<1>(b);
         return a > b;
    });
    for(ll i = 1; i <= n; ++i) AIB::up(L[i], i);
    for(ll i = 1, dr = n; i <= m; ++i) {
        while(dr > get<1>(Q[i])) {
            AIB::up(UnL[dr], V[UnL[dr]]);
            --dr;
        }
        R[get<2>(Q[i])] = AIB::query(get<0>(Q[i]), get<1>(Q[i]));
    }
    for(ll i = 1; i <= m; ++i)
        fo << R[i] % 666013 << "\n";
    return 0;
}