#include <fstream>
#include <algorithm>
using namespace std;

const int MAX_N = 100002;
const int MOD = 666013;

struct Query {
    int x, y, ind;
};

int N, K, M;
int v[MAX_N], A[MAX_N], sol[MAX_N], pos[MAX_N];
Query B[MAX_N];

inline bool Query_cmp(Query a, Query b) {
    return a.y < b.y;
}

void update(int pos, int val) {
    for( ; pos <= N; pos += pos ^ (pos & (pos - 1))) {
        A[pos] += val;
        if(A[pos] < 0)
            A[pos] += MOD;
        A[pos] %= MOD;
    }
}

int query(int pos) {
    int ret = 0;

    for( ; pos; pos -= pos ^ (pos & (pos - 1))) {
        ret += A[pos];
        ret %= MOD;
    }

    return ret;
}

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

    f >> N >> K >> M;
    for(int i = 1; i <= N; ++i)
        f >> v[i];
    for(int i = 1; i <= M; ++i) {
        f >> B[i].x >> B[i].y;
        B[i].ind = i;
    }

    sort(B + 1, B + M + 1, Query_cmp);
    for(int i = 1; i <= M; ++i) {
        for(int j = B[i - 1].y + 1; j <= B[i].y; ++j) {
            if(pos[v[j]])
                update(pos[v[j]], -v[j]);
            pos[v[j]] = j;
            update(j, v[j]);
        }

        sol[B[i].ind] = query(B[i].y) - query(B[i].x - 1);
        while(sol[B[i].ind] < 0)
            sol[B[i].ind] += MOD;
    }

    for(int i = 1; i <= M; ++i)
        g << sol[i] << "\n";

    f.close();
    g.close();

    return 0;
}