#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

const int SZ = 100000;
const int MOD = 666013;

struct Node {
	int val;
	int st;
	int en;
	Node *next = NULL;
	Node(int u) {
		val = u;
	}
	Node(int u, int s, int e) {
		val = u;
		st = s;
		en = e;
	}
	bool over() {
		return st == en;
	}
};
typedef Node* PNode;

class List {
	PNode head = NULL;
	PNode tail = NULL;
public:
	PNode& add(int u) {
		if (head) {
			tail->next = new Node(u);
			tail = tail->next;
		}
		else {
			head = tail = new Node(u);
		}
		return tail;
	}
	PNode& top() {
		return head;
	}
	PNode& next(PNode &ant) {
		if (ant) {
			return ant->next;
		}
		else {
			return ant;
		}
	}
	PNode& rem(bool free = false) {
		PNode p = head;
		if (head && head->next) {
			head = head->next;
		}
		else {
			head = tail = NULL;
		}
		if (free) {
			delete p;
		}
		return head;
	}
	PNode& rem(PNode &ant, bool free = false) {

		if (ant) {
			PNode p = ant->next;
			if (tail ==  p) {
				tail = ant;
			}
			ant->next = p->next;
			if (free) {
				delete p;
			}
			return ant->next;
		}
		else {
			return rem(free);
		}
	}
};

struct Range {
	int left;
	int right;
	int sum;
};
typedef Range* PRange;

int orig[SZ + 1];
int cnt[SZ + 1];
long long sum[SZ + 1];
Range query[SZ];
PRange pquery[SZ];
PNode dups[SZ / 2];
int where_dups[SZ + 1];
int seq[SZ];
int query_dup[SZ + 1];

bool cmp(PRange &a, PRange &b) {
	return a->left < b->left;
}

bool search(PNode &p, PRange &q) {
	int mid, en = p->en - 1;
	if (q->left <= seq[p->st]) {
		return q->right >= seq[p->st];
	}
	if (q->left > seq[en]) {
		p->st = p->en;
		return false;
	}
	if (en - p->st == 1) {
		return q->right >= seq[en];
	}
	while (en - p->st > 1) {
		mid = p->st + (en - p->st) / 2;
		if (q->left > seq[mid]) {
			p->st = mid;
		}
		else {
			en = mid;
		}
	}
	return q->right >= seq[p->st + 1];
}

int main(int argc, char** argv) {
	int M, N, K;
	int i, j, u, ndup = 0;
	int min_left, max_right;
	long long uu;
	PNode p, p_ant;
	PRange q;
	List list;
	ifstream f("distincte.in");
	f >> N >> K >> M;
	for (i = 1; i <= N; i++) {
		f >> u;
		orig[i] = u;
		cnt[u]++;
		if (cnt[u] == 2) {
			dups[ndup] = list.add(u);
			where_dups[u] = ndup;
			ndup++;
		}
	}
	min_left = N + 1;
	max_right = 0;
	for (i = 0; i < M; i++) {
		q = &query[i];
		pquery[i] = q;
		f >> q->left >> q->right;
		if (q->left < min_left) {
			min_left = q->left;
		}
		if (q->right > max_right) {
			max_right = q->right;
		}
	}
	f.close();
	j = 0;
	for (i = 0; i < ndup; i++) {
		dups[i]->st = j;
		dups[i]->en = j;
		j += cnt[dups[i]->val];
	}
	for (i = min_left; i <= max_right; i++) {
		u = orig[i];
		sum[i] = sum[i - 1];
		if (cnt[u] > 1) {
			p = dups[where_dups[u]];
			seq[p->en] = i;
			p->en++;
		}
		else {
			sum[i] += u;
		}
	}
	sort(pquery, pquery + M, cmp);
	K = log(N) / log(2) + 1;
	for (i = 0; i < M; i++) {
q = pquery[i];
		uu = sum[q->right] - sum[q->left - 1];
		if (q->right - q->left < K) {
			for (j = q->left; j <= q->right; j++) {
				u = orig[j];
				if (cnt[u] > 1 && query_dup[u] != i + 1) {
					query_dup[u] = i + 1;
					uu += u;
				}
			}
		}
		else {
			p_ant = NULL;
			p = list.top();
			while (p) {
				if (search(p, q)) {
					uu += p->val;
				}
				if (p->over()) {
					p = list.rem(p_ant);
				}
				else {
					p_ant = p;
					p = list.next(p);
				}
			}
		}
		q->sum = uu % MOD;
	}
	ofstream g("dictincte.out");
	for (i = 0; i < M; i++) {
		g << query[i].sum << '\n';
	}
	g.close();
	return 0;
}