#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=400005;
int lc[N*33],rc[N*33],sum[N*33],V[N*33],cnt[N*33],root[N];
const int lim=2000000001;
const int S=1000000001;
int tot=0;
int insert(int p1,int p2,int l,int r,int v)
{
	if(r<l)
	return 0;
	p2=++tot;
	cnt[p2]=cnt[p1];
	int mid=(l+r)/2;
	V[p2]=mid;
	if(v<mid)
	{
	rc[p2]=rc[p1];
	lc[p2]=insert(lc[p1],lc[p2],l,mid-1,v);
	}
	else if(v>mid)
	{
	lc[p2]=lc[p1];
	rc[p2]=insert(rc[p1],rc[p2],mid+1,r,v);
	}
	else
	{
	cnt[p2]++;
	lc[p2]=lc[p1];rc[p2]=rc[p1];
	}
	sum[p2]=sum[lc[p2]]+sum[rc[p2]]+cnt[p2];
	return p2;
}
int query(int p1,int p2,int k)
{
	while(1)
	{
		int s1=sum[lc[p2]]-sum[lc[p1]];
		int s2=cnt[p2]-cnt[p1];
		if(s1>k||(s1==k&&s2==0))
		{
			p1=lc[p1];
			p2=lc[p2];
		}
		else if(s1+s2<k)
		{
			p1=rc[p1];
			p2=rc[p2];
			k-=s1+s2;
		}
		else
		return V[p2];
	}
}
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int v;
		cin>>v;
		v+=S;
		root[i]=insert(root[i-1],0,1,lim,v);	
	}
	for(int i=1;i<=m;i++)
	{
		int l,r,k;
		cin>>l>>r>>k;
		cout<<query(root[l-1],root[r],k)-S<<endl;
	}
	return 0;
}

错误情况是在比较靠后的询问会WA