#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5;
const int modulo = 666013;

inline int lsb(int X) {
	return X & (-X);
}

int aib[nmax+5], n, v[nmax+5], last[nmax+5], ans[nmax+5];
vector<vector<pair<int,int>>> qu(nmax+5);

void update(int pos, int val) {
	for(int i=pos; i<=n; i+=lsb(i))
		aib[i] = (aib[i] + val) % modulo;	
}

int query(int pos) {
	int rez = 0;
	for(int i=pos; i>=1; i-=lsb(i))
		rez = (rez + aib[i]) % modulo;
	return rez;
}

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

	int k, m; f >> n >> k >> m;
	for(int i=1; i<=n; i++) f >> v[i];
	for(int i=1; i<=m; i++) {
		int x, y; f >> x >> y;
		qu[x].emplace_back(y,i);
	}
	for(int i=n; i>=1; i--) {
		if(last[v[i]]) update(last[v[i]], -v[i]);
		last[v[i]] = i;
		update(i, v[i]);
		for(auto x : qu[i])
			ans[x.second] = query(x.first) - query(i-1);
	}
	for(int i=1; i<=m; i++) if(ans[i] < 0) ans[i] += modulo;
	for(int i=1; i<=m; i++) g << ans[i] << "\n";
	return 0;
}