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

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