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

struct dbg {
    template <typename type>
        inline void operator << (const type a) {
            #ifndef INFOARENA
                cout << "\033[1;31m" << a << "\033[0m\n";
            #endif
        }
} debug;

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

const int MAX = 1e5 + 5;
const int MOD = 666013;

inline int make(const int a) {
    if (a > 0) {
        return a % MOD;
    } else {
        return ((a % MOD) + MOD) % MOD;
    }
}

struct query {
    int x, y, i, s;
    query() {
        x = y = i = s = 0;
    }
};

struct bit {
    int a[MAX];
    inline void update(const int pos, const int val) {
        for (int i = pos; i < MAX; i |= i - 1, ++i) {
            a[i] = make(a[i] + val);
        }
    }
    inline int get(const int pos) {
        int s = 0;
        for (int i = pos; i >= 1; i &= i - 1) {
            s = make(s + a[i]);
        }
        return s;
    }
    inline int query(const int left, const int right) {
        return make(get(right) - get(left - 1));
    }
} d;

int n, k, m;
int a[MAX], b[MAX];
query q[MAX];

int main() {
    fin >> n >> k >> m;
    for (int i = 1; i <= n; ++i) {
        fin >> a[i];
    }
    for (int i = 1; i <= m; ++i) {
        fin >> q[i].x >> q[i].y;
        q[i].i = i;
    }
    sort(q + 1, q + m + 1,
        [&] (const query &a, const query &b) {
            return a.y < b.y;
        }
    );
    for (int i = 1; i <= m; ++i) {
        for (int j = q[i - 1].y + 1; j <= q[i].y; ++j) {
            if (b[a[j]] != 0) {
                d.update(b[a[j]], -a[j]);
            }
            d.update(j, a[j]);
            b[a[j]] = j;
        }
        q[i].s = d.query(q[i].x, q[i].y);
    }
    sort(q + 1, q + m + 1,
        [&] (const query &a, const query &b) {
            return a.i < b.i;
        }
    );
    for (int i = 1; i <= m; ++i) {
        fout << q[i].s << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}