データ構造テンプレート

const int M=300000;
int T[M+M+500];
void add(int l,int r,int v)
{
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1)
	{
		if(~l&1)T[l^1]+=v;
		if(r&1)T[r^1]+=v;
	}
}
int query(int n)
{
	int ans=0;
	for(n+=M;n;n>>=1)ans+=T[n];
	return ans;
}

const int M=5e6+5;
const int INF=0x3f3f3f3f;
int T1[M+M+50],T2[M+M+50];
void modify(int n,int v){
	for(T1[n+=M]=v,n>>=1;n;n>>=1)
		T1[n] = T1[n+n] + T1[n+n+1];
	for(T2[n+=M]=v,n>>=1;n;n>>=1)
		T2[n] = max(T2[n+n] , T2[n+n+1]);
} 
int query_sum(int l,int r){
	int ans=0;
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
		if(~l&1)ans+=T1[l^1];
		if(r&1)ans+=T1[r^1];
	}
	return ans;
}
int query_max(int l,int r){
	int ans=-INF;
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
		if(~l&1)ans=max(ans,T2[l^1]);
		if(r&1)ans=max(ans,T2[r^1]);
	}
	return ans;
}

typedef long long ll;//              
const int N=2e5+5;
struct node{
	int l,r;
	ll sum,lazy;
	
}tree[N<<2];
ll a[N];
inline void push_down(int);
inline void build(int i,int l,int r){
	tree[i].l=l;tree[i].r=r;tree[i].lazy=0;
	if(l==r){
		tree[i].sum=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
	
}
inline void add(int i,int l,int r,ll k){
	if(tree[i].l>=l && tree[i].r<=r){
		tree[i].sum+=k*(tree[i].r-tree[i].l+1);
		tree[i].lazy+=k;
		return ;
	}
	//if(tree[i].rr)return;
	push_down(i);
	if(tree[i*2].r>=l)add(i*2,l,r,k);
	if(tree[i*2+1].l<=r)add(i*2+1,l,r,k);
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
}
inline void push_down(int i){
	if(tree[i].lazy!=0){
		tree[i*2].lazy+=tree[i].lazy;
		tree[i*2+1].lazy+=tree[i].lazy;
		int mid=(tree[i].l+tree[i].r)>>1;
		tree[i*2].sum+=tree[i].lazy*(mid-tree[i*2].l+1);
		tree[i*2+1].sum+=tree[i].lazy*(tree[i*2+1].r-mid);
		tree[i].lazy=0;
	}
}
inline ll search(int i,int l,int r){
	if(tree[i].l>=l && tree[i].r<=r){
		return tree[i].sum;
	}
	if(tree[i].r<l || tree[i].l>r)return 0;
	push_down(i);
	ll ans=0;
	if(tree[i*2].r>=l)ans+=search(i*2,l,r);
	if(tree[i*2+1].l<=r)ans+=search(i*2+1,l,r);
	return ans;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=2e5+50;
LL sum[maxn];
const int N=2e5+7;
struct Tree{
    LL minn,lazy;
}tree[N<<2];
inline void build(int root,int l,int r){
    if(l==r){
        tree[root].minn=sum[l];//1~l a[i]  
        tree[root].lazy=0;
        return;
    }
    int mid=(l+r)>>1;
    build((root<<1),l,mid);
    build((root<<1|1),mid+1,r);
    tree[root].minn=min(tree[(root<<1)].minn,tree[(root<<1|1)].minn);//up
    return;
}
inline void pushdown(int root){
    if(!tree[root].lazy)
        return;
    tree[(root<<1)].minn+=tree[root].lazy;
    tree[(root<<1|1)].minn+=tree[root].lazy;
    tree[(root<<1)].lazy+=tree[root].lazy;
    tree[(root<<1|1)].lazy+=tree[root].lazy;
    tree[root].lazy=0;
    return;
}
inline void change(int root,int l,int r,int x,int y,int val){
    if(r<x||l>y)
        return;
    if(x<=l&&r<=y){
        tree[root].minn+=val;
        tree[root].lazy+=val;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(root);
    change((root<<1),l,mid,x,y,val);
    change((root<<1|1),mid+1,r,x,y,val);
    tree[root].minn=min(tree[(root<<1)].minn,tree[(root<<1|1)].minn);//up
    return;
}

#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn = 2e5+5;
int a[maxn];
vector<int> v;
int cnt,root[maxn];
struct node{
	int l,r,sum;
}hjt[maxn*40];
inline int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
inline void insert(int l,int r,int pre,int &now,int p){
	hjt[++cnt]=hjt[pre];
	now=cnt;
	hjt[cnt].sum++;
	if(l == r)return ;
	int mid=(l + r) >> 1;
	if(p<=mid)insert(l,mid,hjt[pre].l,hjt[now].l,p);
	else insert(mid+1,r,hjt[pre].r,hjt[now].r,p);
	
}
inline int query(int l,int r,int L,int R,int k){
	if(l == r)return l;
	int tmp = hjt[hjt[R].l].sum-hjt[hjt[L].l].sum;
	int mid = (l + r)>>1;
	if(k<=tmp)return query(l,mid,hjt[L].l,hjt[R].l,k);
	else return query(mid+1,r,hjt[L].r,hjt[R].r,k-tmp);
}
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		v.push_back(a[i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	int l,r,k;
	for(int i=1;i<=n;i++){
		insert(1,n,root[i-1],root[i],getid(a[i]));
	}
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&l,&r,&k);
		printf("%d
",v[query(1,n,root[l-1],root[r],k)-1]);
	}
}

#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<algorithm>
#include<set>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<iomanip>
#include<stack>
#define debug(x) cout << "[" << #x <<": " << (x) <<"]"<< endl
#define pii pair<int,int>
#define clr(a,b) memset((a),b,sizeof(a))
#define rep(i,a,b) for(int i = a;i < b;i ++)
#define pb push_back
#define MP make_pair
#define LL long long
#define ull unsigned LL
#define ls i << 1
#define rs (i << 1) + 1
#define fir first
#define sec second
#define CLR(a) while(!(a).empty()) a.pop()
 
using namespace std;
 
const int maxn = 1e5 + 10;
const int M = maxn * 40;
int T[maxn];///T[i]   i        
int lson[M],rson[M],c[M];///C[i]    i     ,         sum
int X[maxn],K[maxn];     /// lson[i], rson[i]     i       ,     
int tot = 0,en;          /// tot       
 
inline int read() {
    int X = 0, w = 0;
    char ch = 0;
    while(!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while(isdigit(ch))
        X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    return w ? -X : X;
}
 
int build(int l,int r){
    int rt = tot ++;
    c[rt] = 0;
    if(l != r){
        int mid = (l + r) >> 1;
        lson[rt] = build(l,mid);
        rson[rt] = build(mid + 1,r);
    }
    return rt;
}
 
int update(int rt,int pos,int val){
    int newrt = tot ++,tmp = newrt;
    c[newrt] = c[rt] + val;
    int l = 1,r = en;
    while(l < r){
        int mid = (l + r) >> 1;
        if(pos <= mid){
            lson[newrt] = tot ++;
            rson[newrt] = rson[rt];
            newrt = lson[newrt];
            rt = lson[rt];
            r = mid;
        }
        else {
            rson[newrt] = tot ++;
            lson[newrt] = lson[rt];
            newrt = rson[newrt];
            rt = rson[rt];
            l = mid + 1;
        }
        c[newrt] = c[rt] + val;
    }
    return tmp;
}
 
int query(int lrt,int rrt,int k){//query between lrt and rrt how many numbers less than k; 
    int l = 1,r = en;
    int sum = 0;
    while(l < r){
        int mid = (l + r) >> 1;
        if(X[mid] <= k){
            sum += c[lson[rrt]] - c[lson[lrt]];
            l = mid + 1;
            rrt = rson[rrt];
            lrt = rson[lrt];
        }
        else {
            r = mid;
            lrt = lson[lrt];
            rrt = lson[rrt];
        }
    }
    if(l == r){
        if(X[l] <= k)
            sum += c[rrt] - c[lrt];
    }
    return sum;
}
int main(){
	int n = read(),m=read(); 
        for(int i = 1;i <= n;++ i){
            K[i] = read();
            X[i] = K[i];
        }
        sort(X + 1,X + 1 + n);
        en = unique(X + 1,X + 1 + n) - X - 1;
        tot = 0;
        T[0] = build(1,en);
        for(int i = 1;i <= n;++ i){
            int pos = lower_bound(X + 1,X + 1 + en,K[i]) - X;
            T[i] = update(T[i - 1],pos,1);
        }
        for(int i=1;i<=m;i++){
        	int l,r,k;
        	cin>>l>>r>>k;
        	cout<<query(T[l-1],T[r],k-1)<<endl;
		}
}