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

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

typedef struct interval {
    int x, y, nr;
};

int N, K, M;
int v[MAX_N], A[MAX_N], m[MAX_N], sol[MAX_N];
interval a[MAX_N];

inline bool interval_cmp(interval a, interval b) {
    return (a.y < b.y || (a.y == b.y && a.x < b.x));
}

inline int mod(int &x) {
    if(x >= MOD)
        x -= MOD;
    if(x < 0)
        x += MOD;
    return x;
}

inline void Update(int pos, int val) {
    while(pos <= N) {
        A[pos] += val, A[pos] %= MOD;
        mod(A[pos]);
        pos += pos^(pos&(pos-1));
    }
}

inline int Query(int pos) {
    int Sum = 0;
    while(pos > 0) {
        Sum += A[pos];
        mod(Sum);
        pos -= pos^(pos&(pos-1));
    }

    return Sum;
}

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 >> a[i].x >> a[i].y, a[i].nr = i;

    sort(a+1, a+M+1, interval_cmp);
    for(int q = 1; q <= M; ++q) {
        for(int i = a[q-1].y+1; i <= a[q].y; ++i) {
            if(m[v[i]])
                Update(m[v[i]], -v[i]);
            m[v[i]] = i;
            Update(m[v[i]], v[i]);
        }
        sol[a[q].nr] = Query(a[q].y) - Query(a[q].x-1);
        mod(sol[a[q].nr]);
    }

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

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

    return 0;
}