#include <bits/stdc++.h>

using namespace std;

inline char gc() { // like getchar()
    static char buf[1 << 16];
    static size_t bc, be;
    if (bc >= be) {
        buf[0] = 0, bc = 0;
        be = fread(buf, 1, sizeof(buf), stdin);
    }
    return buf[bc++]; // returns 0 on EOF
}
 
int readInt() {
    int a, c;
    while ((a = gc()) < 40);
    if (a == '-') return -readInt();
    while ((c = gc()) >= 48) a = a * 10 + c - 480;
    return a - 48;
}
 
// from madhur4127
/** Write */
static const int buf_size = 1 << 16;
static int write_pos = 0;
static char write_buf[buf_size];
uint32_t digits10(uint64_t v) {
    int len = 1;
    while (v >= 10000)
        v /= 10000, len += 4;
    return len + (v < 100 ? v >= 10 : 2 + (v >= 1000));
}
unsigned u64ToAsciiTable(uint64_t value) {
    static const char digits[201] = "00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899";
    uint32_t const length = digits10(value);
    uint32_t next = length - 1;
    char *dst = &write_buf[write_pos];
    for (; value >= 100; next -= 2, value /= 100) {
        auto const i = (value % 100) * 2;
        dst[next] = digits[i + 1], dst[next - 1] = digits[i];
    }
    // Handle last 1-2 digits
    if (value < 10) {
        dst[next] = '0' + value;
    } else {
        auto i = uint32_t(value) * 2;
        dst[next] = digits[i + 1], dst[next - 1] = digits[i];
    }
    return length;
}
template <typename T = int> inline void write(T x, char end = 0) {
    if (__builtin_expect(write_pos + 21 >= buf_size, 0)) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    if (x < 0) write<char>('-'), x = -x;
    write_pos += u64ToAsciiTable(x);
    if (end) write<char>(end);
}
template <> inline void write<char>(const char x, char) {
    if (__builtin_expect(write_pos == buf_size, 0)) fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}
template <> inline void write<string>(const string s, char end) {
    for (const char c : s)
        write<char>(c);
    if (end) write<char>(end);
}
struct Flusher {
    ~Flusher() {
        if (write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    }
} flusher;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

const int MOD = 666013;

int block_size;

struct Query {
    int l, r, idx;
    bool operator < (const Query &E) const {
        if(l / (const int)block_size != E.l / (const int)block_size)
            return make_pair(l, r) < make_pair(E.l, E.r);
        return (l / (const int)block_size & 1)? (r < E.r) : (r > E.r);
    }
} q[100001];

int a[100001], F[100001], ans[100001];
int N, K, M;

void add_(int &a, int b) {
    a += b;
    while(a >= MOD)
        a -= MOD;
}

void dec_(int &a, int b) {
    a -= b;
    while(a < 0)
        a += MOD;
}

void solve() {
    N = readInt(), K = readInt(), M = readInt();

    block_size = sqrt(N);
    for(int i = 1;i <= N;a[i] = readInt(), i++);

    for(int i = 1;i <= M;i++)
        q[i].l = readInt(), q[i].r = readInt(), q[i].idx = i;

    sort(q + 1, q + M + 1);
    for(int i = 1, l = 1, r = 0, sum = 0;i <= M;i++) {
        while(l > q[i].l) {
            if(++F[a[--l]] == 1)
                add_(sum, a[l]);
        }

        while(l < q[i].l) {
            if(--F[a[l++]] == 0)
                dec_(sum, a[l - 1]);
        }

        while(r < q[i].r) {
            if(++F[a[++r]] == 1)
                add_(sum, a[r]);
        }

        while(r > q[i].r) {
            if(--F[a[r--]] == 0)
                dec_(sum, a[r + 1]);
        }

        ans[q[i].idx] = sum;
    }

    for(int i = 1;i <= M;i++)
        write(ans[i]), write('\n');
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    Open("distincte");

    int T = 1;
    for(;T;T--) {
        solve();
    }

    return 0;
}