#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
typedef long long int64;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
const int MAX_N = 100100;
const int HELL = 666013;
struct question {
    int x, y;
    int pos;
    bool operator < (const question &other) const {
        return y < other.y;
    }
} q[MAX_N];
int64 aib[MAX_N];
int64 sol[MAX_N];
int N, K, M;
int v[MAX_N];
int last[MAX_N];
void read(), solve(), print();
void update(int pos, int val);
int64 query(int pos);

int main() {
    read();
    solve();
    print();
    return 0;
}

void read() {
    ifstream fin("distincte.in");
    fin >> N >> K >> M;
    for (int i = 1; i <= N; ++i) {
        fin >> v[i];
    }
    for (int i = 1; i <= M; ++i) {
        fin >> q[i].x >> q[i].y;
        q[i].pos = i;
    }
}

void solve() {
    sort(q + 1, q + M + 1);
    int l = 1;
    for (int i = 1; i <= M; ++i) {
        while (l <= q[i].y) {
            if (last[v[l]] > 0) 
                update(last[v[l]], -v[l]);
            update(l, v[l]);
            last[v[l]] = l;
            ++l;
        }
        sol[q[i].pos] = (query(q[i].y) - query(q[i].x - 1));
    }
}

void print() {
    ofstream fout("distincte.out");
    for (int i = 1; i <= M; ++i) {
        fout << sol[i] % HELL<< '\n';
    }
}

void update(int pos, int val) {
    for (int i = pos; i <= N; i += (i & -i)) {
        aib[i] += val;
    }
}

int64 query(int pos) {
    int64 result = 0;
    for (int i = pos; i > 0; i -= (i & -i)) {
        result += aib[i];
    }
    return result;
}