样例无法通过，全部输出30519

#include<cstdio>
#include<unistd.h>
#define re register
const int MAXn = 2e5;
const int MAXm = 2e5;
const int MAXai = 1e9;

template <class T>
inline void read(T &a) {
	register char c;while (c = getchar(), (c < '0' || c > '9') && c != '-');register bool f = c == '-';register T x = f ? 0 : c - '0';while (c = getchar(), c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + c - '0';}a = f ? -x : x;
}

int top, t[MAXn + 10];
#define lowbit(x) ((x) & (-(x)))
void BuildUseSum(int *sum) {
	for (re int i = 1; i <= top; ++i) {
		t[i] = sum[i] - sum[i - lowbit(i)];
	}
}
void Add(int p, int v) {
	while (p <= top) {
		t[p] += v;
		p += lowbit(p);
	}
}
int EvaSum(int p) {
	int ans = 0;
	while (p) {
		ans += t[p];
		p -= lowbit(p);
	}
	return ans;
}

int n, m, cnt, cnt1, cnt2, ans[MAXm + 10];
struct Ele {
	int idx, v, l, r, opt;
	Ele(): idx(0), v(0), l(0), r(0), opt(0) {}
	Ele(int idx_, int v_, int l_, int r_, int opt_): 
		idx(idx_), v(v_), l(l_), r(r_), opt(opt_) {}
}a[MAXn + MAXm + 10], a1[MAXn + MAXm + 10], a2[MAXn + MAXm + 10];
void Div(int L, int R, int l, int r) {
	// sleep(0.5);
	// printf ("Div(%d, %d, %d, %d)\n", L, R, l, r);
	if (l > r) return;
	if (L == R) {
		for (re int i = l; i <= r; ++i) {
			if (a[i].opt) {
				ans[a[i].idx] = L;
			}
		}
	} else {
		int mid = (L + R) >> 1;
		cnt1 = cnt2 = 0;
		for (re int i = l; i <= r; ++i) {
			if (!a[i].opt) {
				if (a[i].v <= mid) {
					a1[++cnt1] = a[i];
					Add(a[i].idx, 1);
				} else {
					a2[++cnt2] = a[i];
				}
			} else {
				int x = EvaSum(a[i].r) - EvaSum(a[i].l - 1);
				if (a[i].v <= x) {
					a1[++cnt1] = a[i];
				} else {
					a[i].v -= x;
					a2[++cnt2] = a[i];
				}
			}
		}
		for (re int i = 1; i <= cnt1; ++i) {
			if (!a1[i].opt) {
				Add(a1[i].idx, -1);
			}
		}	
		for (re int i = 1; i <= cnt1; ++i) {
			a[l + i - 1] = a1[i];
		}
		for (re int i = 1; i <= cnt2; ++i) {
			a[l + cnt1 + i - 1] = a2[i];
		}
		Div(L, mid, l, l + cnt1 - 1);
		Div(mid + 1, R, l + cnt1, r);
	}
}


int main() {
	read(n), read(m);
	top = n;
	for (re int i = 1, v; i <= n; ++i) {
		read(v);
		a[++cnt] = Ele(i, v, 0, 0, 0);
	}
	for (re int i = 1, l, r, k; i <= m; ++i) {
		read(l), read(r), read(k);
		a[++cnt] = Ele(i, k, l, r, 1);
	}
	Div(-MAXai, MAXai, 1, cnt);
	for (re int i = 1; i <= m; ++i) {
		printf("%d\n", ans[i]);
	}
}