#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int MOD = 666013;

class Aib {

private:

	vector<int> aib;
	int len;

	int lsb(int x) {

		return (x & (-x));

	}

public:

	Aib(int len) {

		this->len = len;
		aib.resize(len + 5);

	}

	void update(int pos, int val) {

		if (pos == 0)
			return;

		for (int i = pos; i <= len; i += lsb(i))
			aib[i] += val;

	}

	int query(int pos) {

		int sum = 0;

		for (int i = pos; i; i -= lsb(i))
			sum = (sum + aib[pos]) % MOD;

		return sum;

	}

} *aib;

struct Query {

	int left;
	int right;
	int index;

	Query(int left, int right, int index) {

		this->left = left;
		this->right = right;
		this->index = index;

	}

	bool operator < (const Query x) const {

		return this->right < x.right;

	}

};

vector<int> vec, last, solution;
vector< Query > queries;

int main() {

	ifstream fin("distincte.in");
	ofstream fout("distincte.out");

	int n, k, m;
	fin >> n >> k >> m;

	vec.resize(n + 1);
	for (int i = 1; i <= n; ++i)
		fin >> vec[i];

	for (int i = 0; i < m; ++i) {

		int left, right;
		fin >> left >> right;

		queries.push_back(Query(left, right, i));

	}

	sort(queries.begin(), queries.end());

	last.resize(n + 1);
	solution.resize(m);
	aib = new Aib(n);
	for (int i = 0, curr = 1; i < m; ++i) {

		while (curr <= queries[i].right) {

			aib->update(last[vec[curr]], -vec[curr]);
			aib->update(curr, vec[curr]);

			last[vec[curr]] = curr;

			++curr;

		}

		solution[queries[i].index] = (MOD + aib->query(queries[i].right) - aib->query(queries[i].left - 1)) % MOD;

	}

	for (int i = 0; i < m; ++i)
		fout << solution[i] << '\n';

	return 0;

}

//Trust me, I'm the Doctor!