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

const int N = 1e5 + 5;
const int mod = 666013;

struct Queries {
	int x, y, ind;
	bool operator<(const Queries& a) const{
		return y<a.y;
	}
};

int sum(int a, int b) {
	int s = a + b;
	if(s>=mod) s-=mod;
	if(s<0) s+=mod;
	return s;
}

int aib[N], mn[N], v[N], ans[N];
std::vector<Queries>q;

void update(int poz, int val) {
	for(;poz<N;poz+=poz&(-poz)) aib[poz]+=val;
}

int query(int poz) {
	int s = 0;
	for(;poz;poz-=poz&(-poz)) s=sum(aib[poz], s);
	return s;
}

int main() {
	std::ifstream fin("distincte.in");
	std::ofstream fout("distincte.out");
	int n, m, k;
	fin>>n>>k>>m;
	q.resize(m);
	for(int i=1;i<=n;i++) fin>>v[i];
	for(int i=0;i<m;i++) fin>>q[i].x>>q[i].y, q[i].ind = i;
	std::sort(q.begin(), q.end());
	int prev = 1;
	for(Queries a:q) {
		for(;prev<=a.y;prev++) {
			if(!mn[v[prev]]) update(prev, v[prev]);
			else {
				update(mn[v[prev]], -v[prev]);
				update(prev, v[prev]);
			}
			mn[v[prev]] = prev;
		}
		ans[a.ind] = sum(query(a.y),-query(a.x-1));
	}
	for(int i=0;i<m;i++) fout<<ans[i]<<"\n";
}