#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;

constexpr int mod = 666013;

void mod_add(int& x, const int y){
	x += y;
	if(x >= mod){
		x -= mod; } }
	
int norm(const int x){
	if(x < 0){
		return x+mod; }
	return x; }

class aib{
	int n;
	vector<int> buf;
public:
	aib(const int N): n(N), buf(n+1, 0){}
	void update(int p, const int d){
		for(++p; p <= n; p += p&-p){
			mod_add(buf[p], d); } }
	int query(int p){
		int rez = 0;
		for(++p; p > 0; p -= p&-p){
			mod_add(rez, buf[p]); }
		return rez; }
	int query(int st, int dr){
		return norm(query(dr) - query(st-1)); } };

int main(){
	ifstream f("distincte.in");
	ofstream g("distincte.out");

	int n, k, m;
	f >> n >> k >> m;

	vector<int> v(n);
	for(auto& x : v){
		f >> x;
		--x; }

	struct query{ int st, dr, ind; };

	vector<int> rez(m);
	vector<query> qs;
	for(int i = 0, st, dr; i < m; ++i){
		f >> st >> dr;
		qs.push_back((query){st-1, dr-1, i}); }

	vector<int> next(n, n+1), first_of(k, -1);
	{
		vector<int> next_for(k, n+1);
		for(int i = n-1; i >= 0; --i){
			next[i] = next_for[v[i]];
			next_for[v[i]] = i; } }
	for(int i = 0; i < n; ++i){
		if(first_of[v[i]] == -1){
			first_of[v[i]] = i; } }

	aib a(n);

	for(int i = 0; i < k; ++i){
		a.update(first_of[i], i+1); }
	sort(begin(qs), end(qs), [](const query& a, const query& b){
			return a.st < b.st; });
	for(int st = 0, i_q = 0; st < n; ++st){
		for( ; i_q < m && qs[i_q].st == st; ++i_q){
			rez[qs[i_q].ind] = a.query(st, qs[i_q].dr); }
		if(next[st] < n){
			a.update(next[st], v[next[st]]+1); } }

	for(const auto x : rez){
		g << x << '\n'; }
	return 0; }