#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
const int mod = 666013;

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

int mul(int a, int b) {
	return a * (ll)b % mod;
}

const int N = 100000 + 7;
int n, lim, m, aib[N], a[N], last[N], sol[N];

void add_aib(int pos, int x) {
	while (pos <= n) {
		aib[pos] = add(aib[pos], x);
		pos += pos & (-pos);
	}
}

int get(int pos) {
	int res = 0;
	while (pos > 0) {
		res = add(res, aib[pos]);
		pos -= pos & (-pos);
	}
	return res;
}

struct seg {
	int l;
	int r;
	int i;
};

bool operator < (seg a, seg b) {
	return a.r < b.r;
}

seg b[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

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

	cin >> n >> lim >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	for (int i = 1; i <= m; i++) {
		cin >> b[i].l >> b[i].r;
		b[i].i = i;
	}
	sort(b + 1, b + m + 1);

	int curpos = 1;
	for (int i = 1; i <= n; i++) {
    int x = a[i];
    if (last[x] == 0) {
      add_aib(1, x);
      add_aib(i + 1, -x);
    } else {
      add_aib(last[x] + 1, x);
      add_aib(i + 1, -x);
    }
    last[x] = i;
    while (curpos <= m && b[curpos].r == i) {
      sol[b[curpos].i] = get(b[curpos].l);
      curpos++;
    }
	}

	for (int i = 1; i <= m; i++) {
		cout << sol[i] << "\n";
	}

	return 0;
}