#include <cstdio>
#include <algorithm>

using namespace std;

const int MaxN = 100005;
const int Modulo = 666013;

struct query {
    int p, l, r;
    inline bool operator() (query Q1, query Q2) {
        return Q1.l > Q2.l;
    }
};

query Q[MaxN];
int N, NQ, V[MaxN], Next[MaxN];
int BIT[MaxN], Answer[MaxN];

inline void Mod(int &X) {
    if (X >= Modulo)
        X -= Modulo;
}

inline int LSB(int X) {
    return X&(-X);
}

inline void Update(int X, int Value) {
    if (X == 0)
        return;
    for (; X <= N; X += LSB(X))
        BIT[X] += Value, Mod(BIT[X]);
}

inline int Query(int X) {
    int QSum = 0;
    for (; X; X -= LSB(X))
        QSum += BIT[X], Mod(QSum);
    return QSum;
}

void Solve() {
    sort(Q+1, Q+NQ+1, query());
    for (int i = 1, j = N; i <= NQ; ++i) {
        for (; j >= Q[i].l; --j)
            Update(j, V[j]), Update(Next[V[j]], -V[j]), Next[V[j]] = j;
        Answer[Q[i].p] = Query(Q[i].r);
    }
}

void Read() {
    freopen("distincte.in", "r", stdin);
    int K; scanf("%d %d %d", &N, &K, &NQ);
    for (int i = 1; i <= N; ++i)
        scanf("%d", &V[i]);
    for (int i = 1; i <= NQ; ++i)
        scanf("%d %d", &Q[i].l, &Q[i].r), Q[i].p = i;
}

void Print() {
    freopen("distincte.out", "w", stdout);
    for (int i = 1; i <= NQ; ++i)
        printf("%d\n", Answer[i]);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}