// poj2761

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<queue>

#define LL long long

#define lim 1000000000

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=100010;

int n,m,sz,rt[maxn];

struct node {

	int son[2],s;

	int& operator [] (int x) {return son[x];}

}tr[maxn*40];

void build(int &u,int v,int l,int r,int val) {

	u=++sz;

	if (l==r) {tr[u].s=tr[v].s+1;return;}

	int mid=(l+r)>>1;

	if (val<=mid) build(tr[u][0],tr[v][0],l,mid,val),tr[u][1]=tr[v][1];

	else build(tr[u][1],tr[v][1],mid+1,r,val),tr[u][0]=tr[v][0];

	tr[u].s=tr[tr[u][0]].s+tr[tr[u][1]].s;

}

int query(int u,int v,int l,int r,int k) {

	if (l==r) return l;

	int mid=(l+r)>>1,c=tr[tr[v][0]].s-tr[tr[u][0]].s;

	if (c>=k) return query(tr[u][0],tr[v][0],l,mid,k);

	else return query(tr[u][1],tr[v][1],mid+1,r,k-c);

}

int main() {

	scanf("%d%d",&n,&m);

	for (int x,i=1;i<=n;i++) {

		scanf("%d",&x);

		build(rt[i],rt[i-1],-lim,lim,x);

	}

	for (int x,y,k,i=1;i<=m;i++) {

		scanf("%d%d%d",&x,&y,&k);

		printf("%d\n",query(rt[x-1],rt[y],-lim,lim,k));

	}

	return 0;

}

// poj2761

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=100010;

struct ask {int l,r,k,id;}t[maxn];

struct data {int w,id;}a[maxn];

int pos[maxn],cnts[maxn],b[maxn],p[maxn],ma[maxn],ans[maxn],n,m,s,q,block;

bool wcmp(data a,data b) {

    return a.w<b.w;

}

bool poscmp(ask a,ask b) {

    return pos[a.l]==pos[b.l] ? a.r<b.r : pos[a.l]<pos[b.l];

}

void build() {

    block=(int)sqrt((float)m);

    for (int i=1;i<=m;i++) pos[i]=(i-1)/block+1;

    s=m%block ? m/block+1 : m/block;

    for (int i=1;i<=s;i++) cnts[i]=0;

}

void update(int x,int val) {

    cnts[pos[x]]+=val;

    b[x]+=val;

}

int query(int k) {

    int tot=0;

    for (int i=1;i<=s;i++) {

        tot+=cnts[i];

        if (tot>=k) {

            tot-=cnts[i];

            for (int j=(i-1)*block+1;j<=min(i*block,m);j++) {

                if (tot+b[j]>=k) return ma[j];

                else tot+=b[j];

            }

        }

    }

}

int main() {

    scanf("%d%d",&n,&q);

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

    for (int i=1;i<=q;i++) scanf("%d%d%d",&t[i].l,&t[i].r,&t[i].k),t[i].id=i;

    sort(a+1,a+1+n,wcmp);

    m=0;

    ma[p[a[1].id]=++m]=a[1].w;

    for (int i=2;i<=n;i++) {

        if (a[i].w!=a[i-1].w) m++;

        ma[p[a[i].id]=m]=a[i].w;

    }

    block=(int)sqrt((float)n);

    for (int i=1;i<=n;i++) pos[i]=(i-1)/block+1;

    sort(t+1,t+1+q,poscmp);

    build();

    for (int l=1,r=0,i=1;i<=q;i++) {

        for (;r<t[i].r;r++) update(p[r+1],1);

        for (;r>t[i].r;r--) update(p[r],-1);

        for (;l<t[i].l;l++) update(p[l],-1);

        for (;l>t[i].l;l--) update(p[l-1],1);

        ans[t[i].id]=query(t[i].k);

    }

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

    return 0;

}