#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;
struct Query {
int l, r, idx, block_idx;
bool operator < (const Query &E) const {
if(block_idx != E.block_idx)
return make_pair(l, r) < make_pair(E.l, E.r);
return (block_idx & 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();
for(int i = 1;i <= N;a[i] = readInt(), i++);
const int block_size = sqrt(N);
for(int i = 1;i <= M;i++)
q[i].l = readInt(), q[i].r = readInt(), q[i].idx = i, q[i].block_idx = q[i].l / block_size;
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;
}