大致思路是读入每个区间，逐一加入树中，再常规操作求第 k 大，最后再全都删除。
记录。

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

const int N=1e6+5;
int a[N];
int n,m,idx=0;
int x,y,z,root,k;
int opt;

struct node{
	int l,r;  //左右子树 
	int num;  //数字 
	int size; //大小 
	int val;  //权值 
}tr[N];

int new_node(int x){  //新建节点 
	tr[++idx].num=x;  //数字赋值 
	tr[idx].size=1;  //大小赋值 
	tr[idx].val=rand();  //随机权值 
	return idx;  //返回编号 
}

void pushup(int x){  //更新值 
	tr[x].size=1 + tr[tr[x].l].size + tr[tr[x].r].size;
} 

//分裂 
void split(int p,int num,int &x,int &y){  //根节点 数值 小于值的子树的根  大于值的子树的根 
	if(!p){  //如果不存在 
		x=y=0;
		return;
	}
	if(tr[p].num > num){  //如果在左子树 
		y=p;
		split(tr[p].l,num,x,tr[p].l);
	}
	else{  //右子树 
		x=p;
		split(tr[p].r,num,tr[p].r,y);
	}
	pushup(p);
}

//合并 
int merge(int x,int y){  //根  根 一定要满足 x 的数值小于 y 的数值 
	if(!x||!y){  //如果有空树 
		return x+y;
	}
	if(tr[x].val > tr[y].val){  //大根堆 
		tr[x].r=merge(tr[x].r,y);  //把 y 归入 x 的右子树 
		pushup(x);
		return x;
	}
	else{
		tr[y].l=merge(x,tr[y].l);  //把 x 归入 y 的左子树 
		pushup(y);
		return y;
	}
}

void insert(int num){  //插入新节点 
	split(root,num,x,y);  //把树分割为 小于 num  和大于 num 两棵树 
	root=merge( merge(x , new_node(num)) ,y);  //按大小合并 
}  
 
void del(int num){ //删除 
	split(root,num,x,y);  //分成 小于等于 大于 两部分 
	split(x,num-1,x,z);  // x 分成 小于 num 和 等于 num
	z=merge(tr[z].l,tr[z].r); //删除 num 的根节点 
	root=merge(merge(x,z),y); //恢复回去 
}

int num_to_rank(int num){  //找排名 
	split(root,num-1,x,y); //分成 小于 num 和 大于等于 
	int ans=tr[x].size+1;  //答案就是 左子树 +1
	root=merge(x,y);
	return ans;
}

int rank_to_num(int p,int rank){  //找数字 
	if(tr[tr[p].l].size+1==rank){  //找到 
		return tr[p].num;
	}
	else if(tr[tr[p].l].size+1 >= rank){  //在左子树 
		return rank_to_num(tr[p].l,rank);
	}
	else{ //否则在右子树 
		return rank_to_num(tr[p].r,rank-tr[tr[p].l].size-1);
	}
}

int pre(int num){
	split(root,num-1,x,y); //前驱 
	int p=x,ans; //答案在 左子树 
	ans=rank_to_num(x,tr[x].size); 
	root=merge(x,y);
	return ans;
}

int after(int num){ //后继 
	split(root,num,x,y); 
	int p=y,ans; //答案在右子树 
	ans=rank_to_num(y,1); 
	root=merge(x,y);
	return ans;
}

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

	cin>>n>>m;
	for(int i=1;i<=n;i++){
	    cin>>a[i];
	}
	int l,r;
	while(m--){
		cin>>l>>r>>k;
		for(int i=l;i<=r;i++){
			insert(a[i]);
		}
		cout<<rank_to_num(root,k)<<"\n";
		for(int i=l;i<=r;i++){
			del(a[i]);
		}
	}
	return 0;
}