#include <cstdio>
#include <algorithm>
#include <vector>

#define f first
#define s second
#define mp make_pair
#define pb push_back

using namespace std;

const int maxn = 100005;
const int mod = 666013;

int n, m, k;
int A[maxn], sol[maxn], aib[maxn], last[maxn]; 
vector <pair <int, pair <int, int> > > Q;

inline void update(int poz, int val) {
	if(poz == 0) return ;
	for(; poz <= n; poz += (poz & -poz)) {
		aib[poz] = aib[poz] + val;
		if(aib[poz] >= mod) aib[poz] -= mod;
	}
}
inline int query(int poz) {
	int ret = 0;
	for(; poz > 0; poz -= (poz & -poz)) {
		ret = ret + aib[poz];
		if(ret >= mod) ret -= mod;
	}
	return ret;
}
int main() {

	freopen("distincte.in", "r", stdin);
	freopen("distincte.out", "w", stdout);


	scanf("%d%d%d\n", &n, &k, &m);

	for(int i = 1; i <= n; i++)
		scanf("%d\n", &A[i]);

	for(int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		Q.pb(mp(x, mp(y, i)));
	}

	sort(Q.begin(), Q.end());

	for(int i = 0, j = 1; i < m; i++) {
		
		for(; j <= Q[i].s.f; j++) {
			update(last[A[j]], -A[j]);
			update(j, A[j]);
			last[A[j]] = j;
		}
		sol[Q[i].s.s] = query( Q[i].s.f)- query( Q[i].f - 1);
		while(sol[Q[i].s.s] < 0) sol[Q[i].s.s] += mod;
	}
	for(int i = 1; i <= m; i++)
		printf("%d\n", sol[i]);

	return 0;
}