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

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

struct qu {
	int x, y, nr;
};

const int N = 100010;

int n,m,x[N],l[N],r[N],aib[N],k;
qu q[N];

inline bool cmp(const qu &a, const qu &b) {
	return a.y < b.y;
}

inline void update(int poz, const int &val) {
	if(!poz)
		return;
	
	while(poz<=n) {
		aib[poz]+=val;
		poz += poz&(-poz);
	}
}

inline int s(int poz) {
	int rez = 0;
	
	while(poz) {
		rez+=aib[poz];
		poz -= poz&(-poz);
	}
	
	return rez;
}

inline int query(const int &pozx, const int &pozy) {
	return s(pozy) - s(pozx-1);
}

int main() {
	int i,xx,y,j = 1;
	
	in >> n >> k >> m;
	
	for(i = 1; i<=n; ++i)
		in >> x[i];
	
	for(i = 1; i<=m; ++i) {
		in >> xx >> y;
		
		q[i].x = xx; q[i].y = y;
		q[i].nr = i;
	}
	
	sort(q + 1, q + m + 1, cmp);
	
	for(i = 1; i<=m; ++i) {
		while(j<=q[i].y) {
			
			update(l[x[j]], -x[j]);
			update(j, x[j]);
			l[x[j]] = j;
			
			++j;
		}
		
		r[q[i].nr] = query(q[i].x, q[i].y);
	}
	
	for(i = 1; i<=m; ++i)
		out << r[i]%666013 << "\n";
	
	return 0;
}