#include <iostream>
#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

struct classcomp {
	bool operator () (const pair <int, int>& a, const pair <int, int>& b) const {
		return (a.first > b.first);
	}
} ;

multiset <pair <int, int>, classcomp> myset;

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

ifstream fin(iname);

int A[MAXN], lastvp[MAXN];

int Aib[MAXN], Ret[MAXM];

bool myrangecomp(const pair <pair <int, int>, int> a, const pair <pair <int, int>, int> b) {
	return (a.first.first > b.first.first);
}

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;

	/* 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;
	FORR (i, N, 1) {
		myset.insert(MP(lastvp[A[i]], i));
		lastvp[A[i]] = i;
	}

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

	multiset <pair <int, int>, classcomp>::iterator it;
	FOR (i, 0, M - 1) {
		int a = Q[i].first.second;
		int b = Q[i].first.first;
		while (myset.size() && (*(it = myset.begin())).first > b) {
			insert((*it).second, N);
			myset.erase(myset.begin());
		}
        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;
}