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

ifstream fin("distincte.in");
ofstream fout("distincte.out");

#define MAX 100005
int n, k, m, AIB[MAX], A[MAX], last[MAX];
long long sol[MAX];

void update(int p, int v) {
    for (int i = p; i <= n; i += i & (-i)) {
        AIB[i] += v;
    }
}

long long sum(int poz) {
    long long s = 0;
    for (int i = poz; i > 0; i -= i & (-i)) {
        s += AIB[i];
    }

    return s;
}

int cb(int val) {
    int ans = 0;

    for (int bitmask = 1 << 20; bitmask > 0; bitmask /= 2) {
        if (ans + bitmask <= n && sum(ans + bitmask - 1) < val) {
            ans += bitmask;
        }
    }

    return ans;
}

struct task_type {
    pair<int, int> range;
    int pos;
};

bool cmp(task_type p, task_type q) {
    if (p.range.second < q.range.second) {
        return true;
    } else if (p.range.second == q.range.second) {
        return (p.range.first <= q.range.first);
    }

    return false;
}

vector<task_type> query;

int main() {
    fin >> n >> k >> m;

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

    for (int i = 1; i <= m; i++) {
        task_type task;
        fin >> task.range.first >> task.range.second;
        task.pos = i;
        query.push_back(task);
    }

    sort(query.begin(), query.end(), cmp);

    int p = 0;

    for (auto it = query.begin(); it != query.end(); it++) {
        while (p < (*it).range.second) {
            p++;

            if (last[A[p]]) {
                update(last[A[p]], -A[p]);
            }

            last[A[p]] = p;
            update(p, A[p]);
        }

        sol[(*it).pos] = (sum(p) - sum((*it).range.first - 1)) % 666013;
    }

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

    return 0;
}