求调qaq
目前感觉是替罪羊树的问题，但是替罪羊树貌似没有敲错啊……

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 9,M = 5e4 + 9;

#define gc getchar
inline int read() {
	int c = gc(), t = 1, n = 0;
	while(isspace(c)) { c = gc(); }
	if(c == '-') { t = -1, c = gc(); }
	while(isdigit(c)) { n = n * 10 + c - '0', c = gc(); }
	return n * t;
}
#undef gc

int n,m,len,l,r,k,nl,nr;
int a[N],ans[M];
int broot = 0;

struct moque {
	int l,r,k,bl,id;
}q[M];

namespace SGT {
	int cnt = 0,crt[N],rt;
	struct node {
		int l,r,size,last,same,val;
		node() { val = 0; l = r = 0; last = same = 0; }
	}t[N];
	
	#define ls(x) t[x].l
	#define rs(x) t[x].r 
	#define alpha 0.75
	
	inline void push_up(int u) {
		t[u].size = t[ls(u)].size + t[rs(u)].size + t[u].same;
		t[u].last = t[ls(u)].last + t[rs(u)].last + t[u].same;
	}
	
	inline bool judge(int u) {
		return (t[u].same && (alpha * (double)t[u].size < (double)max(t[ls(u)].size,t[rs(u)].size) || (double)t[u].last < (double)alpha * t[u].size));
	}
	
	inline void unfold(int u) {
		if(!u) return;
		unfold(ls(u));
		if(t[u].same) crt[++rt] = u;
		unfold(rs(u));
	}
	
	inline int rebuild(int l,int r) {
		if(l == r) return 0;
		int mid = (l + r) >> 1;
		ls(crt[mid]) = rebuild(l,mid);
		rs(crt[mid]) = rebuild(mid + 1,r);
		push_up(crt[mid]);
		return crt[mid];
	}
	
	inline void bal(int &u) {
		rt = 0; unfold(u); u = rebuild(1,rt + 1);
	}
	
	inline void insert(int &u,int x) {
		if(!u) {
			u = ++cnt;
			if(!broot) broot = 1;
			t[u].val = x; ls(u) = rs(u) = 0; t[u].last = t[u].same = t[u].size = 1;
		}else {
			if(t[u].val == x) t[u].same++;
			else if(t[u].val > x) insert(ls(u),x);
			else insert(rs(u),x);
			push_up(u);
			if(judge(u)) bal(u);
		}
	}
	
	inline void del(int &u,int x) {
		--t[u].last;
		if(t[u].val == x) --t[u].same;
		else {
			if(t[u].val > x) del(ls(u),x);
			else del(rs(u),x);
		}
		push_up(u);
		if(judge(u)) bal(u);
	}
	
	inline int at(int u,int x) {
		if(ls(u) == rs(u)) return t[u].val;
		if(x <= t[ls(u)].last) return at(ls(u),x);
		else if(x > t[ls(u)].last && t[ls(u)].last + t[u].same >= x) return t[u].val;
		else return at(rs(u),x - t[u].same - t[ls(u)].last);
	}
}; using namespace SGT;

bool cmp(moque u,moque v) {
	if(u.bl != v.bl) return u.bl < v.bl;
	else {
		if(u.bl & 1) return u.r < v.r;
		else return u.r > v.r;
	}
}

int main() {
	n = read(); m = read(); len = pow(n,0.5);
	for(int i = 1;i <= n;i++) a[i] = read();
	for(int i = 1;i <= m;i++) {
		l = read(); r = read(); k = read();
		q[i].l = l; q[i].r = r; q[i].k = k; q[i].id = i; q[i].bl = (l - 1) / len + 1;
	}
	sort(q + 1,q + m + 1,cmp);
	l = 1; r = 0;
	for(int i = 1;i <= m;i++) {
		nl = q[i].l; nr = q[i].r;
		while(l < nl) del(broot,a[l++]);
		while(l > nl) insert(broot,a[--l]);
		while(r > nr) del(broot,a[r--]);
		while(r < nr) insert(broot,a[++r]);
		ans[q[i].id] = at(broot,q[i].k);
	}
	for(int i = 1;i <= m;i++) {
		printf("%d\n",ans[i]);
	}
	return 0;
}