注意值域有 1e9 ，要离散化，最后输出的时候要搞回去。

```cpp
//Author: RingweEH
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define db double
using namespace std;

#define lowbit(x) ((x)&(-x))
const int N=1e5+10,INF=0x3f3f3f3f;
int n,m,a[N],tr[N],ans[N],tot=0,tmp[N];
struct Operation
{ 
	int tim,opt,l,r,val; 
	Operation( int _tim=0,int _opt=0,int _l=0,int _r=0,int _val=0 )
		: tim(_tim),opt(_opt),l(_l),r(_r),val(_val) {}
//opt=0(insert),2(query)
//val:insert x,query rk k;
}q[N*2],le[N*2],ri[N*2];
void Add( int x,int v ) { for(;x<=n;x+=lowbit(x)) tr[x]+=v; }
int Query(int x){int res=0;for(;x;x-=lowbit(x))res+=tr[x];return res;}

void Solve( int ql,int qr,int l,int r )
{//二分询问和答案,插入删除直接做，查询如果比rk小那么答案就在右区间，否则在左区间。
	if ( l==r )
	{
		for ( int i=ql; i<=qr; i++ )
			if ( q[i].opt==2 ) ans[q[i].tim]=l;
		return;
	}
	int mid=(l+r)>>1,lcnt=0,rcnt=0,i,tmp;
	for ( i=ql; i<=qr; i++ )
	{
		if ( q[i].opt==0 ) //insert
		{
			if ( q[i].val<=mid ) le[++lcnt]=q[i],Add(q[i].l,1);
			else ri[++rcnt]=q[i];
		}
		else	//query
		{
			tmp=Query(q[i].r)-Query(q[i].l-1);
			if ( tmp<q[i].val ) q[i].val-=tmp,ri[++rcnt]=q[i];
			else le[++lcnt]=q[i];
		}
	}
	for ( i=1; i<=lcnt; i++ ) 	//recover
	{
		q[ql+i-1]=le[i];
		if ( le[i].opt==0 ) Add(le[i].l,-1);
	}
	for ( i=1; i<=rcnt; i++ ) q[ql+lcnt+i-1]=ri[i];
	if ( lcnt ) Solve(ql,ql+lcnt-1,l,mid);
	if ( rcnt ) Solve(ql+lcnt,qr,mid+1,r);
}

int main()
{
//freopen( "exam.in","r",stdin );

	scanf("%d%d",&n,&m);
	for ( int i=1; i<=n; i++ ) scanf("%d",&a[i]),tmp[i]=a[i];

	sort(tmp+1,tmp+1+n); int tcnt=unique(tmp+1,tmp+1+n)-tmp-1;
	for ( int i=1; i<=n; i++ ) a[i]=lower_bound(tmp+1,tmp+1+tcnt,a[i])-tmp;
	for ( int i=1; i<=n; i++ ) q[++tot]=Operation(0,0,i,i,a[i]);
	int lcnt=0,rcnt=0,x,y,rk; char s[2];
	for ( int i=1; i<=m; i++ )
	{
		rcnt++; scanf("%d%d%d",&x,&y,&rk);
		q[++tot]=Operation(rcnt,2,x,y,rk);
	}
	Solve(1,tot,0,INF);

	for ( int i=1 ;i<=rcnt; i++ ) printf("%d\n",tmp[ans[i]] );

	return 0;
}
```