#include <iostream>
#include <fstream>
#include <algorithm>

#define FILEIN "distincte.in"
#define FILEOUT "distincte.out"

using namespace std;

int n, m, k;

struct _ {
    int x;
    int y;
    int i;
} Q[100005];
long long S[100005];
int V[100005];
int L[100005];
int N[100005];
long long AIB[100005];
const int MOD = 666013;

void update(int pos, int val) {
    if (!pos)
        return;

    while (pos <= n) {
        AIB[pos] += val;
        AIB[pos] %= MOD;
        pos += (pos & -pos);
    }
}

long long query(int pos) {
    if (!pos)
        return 0;

    long long ans = 0;
    while (pos) {
        ans += 1LL * AIB[pos];
        ans %= MOD;
        pos -= (pos & -pos);
    }

    return ans;
}

bool cmp(const _& a, const _& b) {
    return a.x < b.x;
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    cin >> n >> k >> m;

    for (int i = 1; i <= n; i++) {
        cin >> V[i];
    }

    for (int i = 1; i <= m; i++) {
        cin >> Q[i].x >> Q[i].y;
        Q[i].i = i;
    }

    sort(Q+1, Q+m+1, cmp);

    for (int i = 1; i <= n; i++) {
        N[L[V[i]]] = i;
        if (!L[V[i]]) {
            update(i, V[i]);
        }
        L[V[i]] = i;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = max(1, Q[i-1].x); j < Q[i].x; j++) {
            update(N[j], V[N[j]]);
        }

        long long ans;

        ans = query(Q[i].y) - query(Q[i].x - 1);
        while (ans < 0)
            ans += MOD;

        S[Q[i].i] = ans;
    }

    for (int i = 1; i <= m; i++) {
        cout << S[i] << '\n';
    }


    return 0;
}