1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
const int maxn = 200005;
int getint() {
	int r = 0, k = 1; char c = getchar();
	for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r * k;
}
struct list_type {
	int to, next;
} list[maxn << 1];
int cnte = 1, h[maxn];
void ins(int x, int y) {
	list[++cnte].to = y;
	list[cnte].next = h[x];
	h[x] = cnte;
}
namespace CM_tree {
	int tot = 0;
	const int maxnode = maxn * 70;
	int lc[maxnode], rc[maxnode], mi[maxnode], tag[maxnode];
	void change(int &x, int y, int l, int r, int ll, int rr) {
		x = ++tot;
		lc[x] = lc[y]; rc[x] = rc[y]; mi[x] = mi[y]; tag[x] = tag[y];
		if (ll <= l && r <= rr) {
			tag[x] ++; mi[x] ++;
			return;
		}
		int mid = (l + r) >> 1;
		if (ll <= mid) change(lc[x], lc[x], l, mid, ll, rr);
		if (rr > mid) change(rc[x], rc[x], mid+1, r, ll, rr);
		mi[x] = min(mi[lc[x]], mi[rc[x]]) + tag[x];
	}
	int query(int x, int l, int r, int ll, int rr, int Tag) {
		if (ll <= l && r <= rr) return mi[x] + Tag;
		int mid = (l + r) >> 1, ret = INF; Tag += tag[x];
		if (ll <= mid) ret = min(ret, query(lc[x], l, mid, ll, rr, Tag));
		if (rr > mid) ret = min(ret, query(rc[x], mid+1, r, ll, rr, Tag));
		return ret;
	}
}
using CM_tree::change;
using CM_tree::query;
int n, m;
int a[maxn], cnt[maxn], val[maxn], root[maxn], tort[maxn];
int tot;
map<int, int> M;
int CountLess (int x) {
	int l = 0, r = tot;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (x <= val[mid]) r = mid - 1;
		else l = mid;
	}
	return cnt[l];
}
int main() {
	freopen("music.in", "r", stdin);
	freopen("music.out", "w", stdout);
	n = getint(); m = getint();
	for (int i = 1; i <= n; ++i) {
		a[i] = getint();
		M[a[i]]++;
	}
	for (map<int, int>::iterator it = M.begin(); it != M.end(); ++it) {
		++tot;
		cnt[tot] = it->second + cnt[tot-1];
		it->second = tot;
		val[tot] = it->first;
		tort[cnt[tot]] = tot;
	}
	for (int i = 1; i <= n; ++i)
		ins(M[a[i]], i);
	for (int i = 1; i <= tot; ++i) {
		int j = h[i];
		if (j) {
			change(root[i], root[i - 1], 1, n, list[j].to - m + 1, list[j].to);
			for (j = list[j].next; j; j = list[j].next) {
				change(root[i], root[i], 1, n, list[j].to - m + 1, list[j].to);
			}
		}
	}
	int lstans = 0, Q = getint(), tmp;
	int L, R, X;
	while (Q--) {
		L = getint(); R = getint(); X = getint();
		X ^= lstans;
		tmp = CountLess(X);
		X = query(root[tort[tmp]], 1, n, L, R, 0);
		printf("%d\n", X);
		lstans = X;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}