#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

typedef long long lint;

struct jeff{
	int a, b;
	int ind;
};

int fun(int a){
	return a & (-a);
}

int n, k, m;
lint va[100041], pre[100041];
jeff je[100041];
struct Fenwick{
	lint tre[100041];
	void addme(int p, lint a){
		if(p != 0){
			for(int i = p; i <= n; i += fun(i)){
				tre[i] += a;
			}
		}
	}
	lint calme(int p){
		lint s = 0;
		for(int i = p; i > 0; i -= fun(i)){
			s += tre[i];
		}
		return s;
	}
	lint betme(int a, int b){
		return calme(b)-calme(a-1);
	}
};
Fenwick fen;

bool cmp(const jeff &lhs, const jeff &rhs){
	return lhs.b < rhs.b;
}

lint mentos[100041];

const lint wow = 666013;

int main(){
	fin >> n >> k >> m;
	for(int i = 1; i <= n; i++){
		fin >> va[i];
	}
	
	for(int i = 0; i < m; ++i){
		fin >> je[i].a >> je[i].b;
		je[i].ind = i;
	}
	sort(je, je+m, cmp);
	
	int rav = 0;
	for(int i = 0; i < m; ++i){
		jeff x = je[i];
		while(rav < x.b){
			lint v = va[++rav];
			fen.addme(pre[v], -v);
			pre[v] = rav;
			fen.addme(pre[v], v);
		}
		mentos[x.ind] = fen.betme(x.a, x.b);
	}
	
	for(int i = 0; i < m; i++){
		fout << mentos[i]%wow << "\n";
	}	
	return 0;
}