#include <fstream>

#include <vector>
#include <set>
#include <algorithm>

using namespace std;

const char iname[] = "distincte.in";
const char oname[] = "distincte.out";

#define FOR(i, a, b)  for (int i = (a); i <= (b); ++ i)
#define FORR(i, b, a) for (int i = (b); i >= (a); -- i)
#define MP make_pair
#define PB push_back

#define MAXN  100005
#define MAXM  100005

vector <pair <int, int> > V;

vector <pair <pair <int, int>, int> > Q;

ifstream fin(iname);

int A[MAXN], lastvp[MAXN], Aib[MAXN], Ret[MAXM];


void insert(int i, const int n) {
	int val = A[i];
	for (; i <= n; i += i ^ (i & (i - 1)))
		if ((Aib[i] += val) >= 666013)
			Aib[i] -= 666013;
}

int query(int i) {
	int sum = 0;
	for (; i > 0; i -= i ^ (i & (i - 1)))
		if ((sum += Aib[i]) >= 666013)
			sum -= 666013;
	return sum;
}

int main(void)
{
	int N, K, M, a, b;

	/* reads the numbers */
	fin >> N >> K >> M;
	FOR (i, 1, N)   fin >> A[i];

	/* process last value position, lastvp[] */
	FOR (i, 1, K)  lastvp[i] = N+1;
	FORR (i, N, 1) {
		V.PB(MP(lastvp[A[i]], i));
		lastvp[A[i]] = i;
	}
	sort(V.begin(), V.end());

    /* reads the queries */
	FOR (i, 1, M)
		fin >> a >> b, Q.PB(MP(MP(b, a), i));
	sort(Q.begin(), Q.end());

	int j = N-1;
	FORR (i, M - 1, 0) {
		a = Q[i].first.second;
		b = Q[i].first.first;
		for (; j >= 0 && V[j].first > b; -- j)
			insert(V[j].second, N);
        Ret[Q[i].second] = query(b) - query(a - 1);
	}

	ofstream fout(oname);

	FOR (i, 1, M)  fout << ((Ret[i] < 0) ? Ret[i] + 666013 : Ret[i]) <<'\n';

	fin.close(), fout.close();

	return 0;
}