#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define MAXN 100010

long n, k, m, l, px, py, v, a[MAXN], b[MAXN], c[MAXN], x[MAXN], y[MAXN], p[MAXN], sol[MAXN], s[250000];

long query(long p, long r, long nod);
int cmp(long i, long j);
void update(long p, long r, long nod);

int main() {
    freopen("distincte.in", "r", stdin);
    freopen("distincte.out", "w", stdout);
    long i, j;
    scanf("%ld %ld %ld", &n, &k, &m);
    for (i = 1; i <= n; ++i) {
        scanf("%ld ", &a[i]);
        b[i] = c[a[i]];
        c[a[i]] = i;
    }
    for (i = 1; i <= m; ++i) {
        scanf("%ld %ld", &x[i], &y[i]);
        p[i] = i;
    }
    sort(p + 1, p + m + 1, cmp);
    for (l = 1; l <= n; l <<= 1);
    j = 1;
    for (i = 1; i <= n; ++i) {
        if (b[i]) {
			px = b[i];
			py = b[i];        
			v = 0;
			update(0, l, 1);
        }
        px = i;
        py = i;
        v = a[i];
        update(1, l, 1);
        while ((j <= m) && (y[p[j]] == i)) {
			px = x[p[j]];
            py = y[p[j]];
            sol[p[j]] = query(1, l, 1); 
            ++j;
        }
    }
    for (i = 1; i <= m; ++i) {
		printf("%ld\n", sol[i]);
	}
    return 0;
}

long query(long p, long r, long nod) {
    if ((px <= p) && (r <= py)) {
		return s[nod];
	} else {
		long q = (p + r) / 2, ret = 0;
		if (px <= q) {
			ret += query(p, q, nod * 2);
		}
		if (py > q) {
			ret += query(q + 1, r, nod * 2 + 1);
		}
		while (ret >= 666013) {
			ret -= 666013;
		}
		return ret;
	}
	return 0;
}

int cmp(long i, long j) {
    return (y[i] < y[j]);
}

void update(long p, long r, long nod) {
	if ((px <= p) && (r <= py)) {
		s[nod] = v;
	} else {
		long q = (p + r) / 2;
		if (px <= q) {
			update(p, q, nod * 2);
		}
		if (py > q) {
			update(q + 1, r, nod * 2 + 1);
		}
		s[nod] = s[nod * 2] + s[nod * 2 + 1];
		while (s[nod] >= 666013) {
			s[nod] -= 666013;
		}
	}
}