// 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 M=10000010;int a[M],b[M],lson[M],rson[M],T[M],c[M];int n,tot,q;int build(int l,int r) {    int k=++tot;    c[k]=0;    if (l==r) return k;    int mid=(l+r)>>1;    lson[k]=build(l,mid);    rson[k]=build(mid+1,r);    return k;}int update(int l,int r,int K,int x) {    int k=++tot;    c[k]=c[K]+1;    if (l==r) return k;    int mid=(l+r)>>1;    if (x<=mid) {        rson[k]=rson[K];        lson[k]=update(l,mid,lson[K],x);    }    else {        lson[k]=lson[K];        rson[k]=update(mid+1,r,rson[K],x);    }    return k;}int query(int l,int r,int k,int K,int x) {    if (l==r) return l;    int mid=(l+r)>>1;    if (c[lson[K]]-c[lson[k]]>=x)        return query(l,mid,lson[k],lson[K],x);    else return query(mid+1,r,rson[k],rson[K],x-c[lson[K]]+c[lson[k]]);}int main() {    while (scanf("%d%d",&n,&q)!=EOF) {        tot=0;        for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];        sort(b+1,b+1+n);        int m=unique(b+1,b+1+n)-b-1;        T[0]=build(1,m);        for (int i=1;i<=n;i++) {            int x=lower_bound(b+1,b+1+m,a[i])-b;            T[i]=update(1,m,T[i-1],x);        }        while (q--) {            int l,r,k;            scanf("%d%d%d",&l,&r,&k);            printf("%d\n",b[query(1,m,T[l-1],T[r],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;}