#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MAX 1000001
vector<ll> seg[MAX];
vector<ll> q;
void build(ll a[],ll low,ll high,ll pos)
{
if(low==high)
{
seg[pos].push_back(a[low]);
return;
}
ll mid=(low+high)/2;
build(a,low,mid,2*pos+1);
build(a,mid+1,high,2*pos+2);
merge(seg[2*pos+1].begin(),seg[2*pos+1].end(),seg[2*pos+2].begin(),seg[2*pos+2].end(),back_inserter(seg[pos]));
}
ll query(ll low,ll high,ll qlow,ll qhigh,ll val,ll pos,ll n)
{
if(qlow>high||qhigh<low)
{
return 0;
}
if(qlow<=low&&qhigh>=high)
{
q.insert(q.end(),seg[pos].begin(),seg[pos].end());
if(qlow==0&&qhigh==n-1)
{
return q[val-1];
}//upper_bound(seg[pos].begin(),seg[pos].end(),val)-seg[pos].begin();
return 0;
}
ll mid=(low+high)/2;
ll a=query(low,mid,qlow,qhigh,val,2*pos+1,n);
ll b=query(mid+1,high,qlow,qhigh,val,2*pos+2,n);
//merge(seg[2*pos+1].begin(),seg[2*pos+1].end(),seg[2*pos+2].begin(),seg[2*pos+2].end(),back_inserter(q));
/*for(ll i=0;i<q.size();i++)
{
cout<<q[i]<<" ";
}
cout<<endl;*/
sort(q.begin(),q.end());
return q[val-1];
}
int main()
{
ll n,m,x,y,k;
cin>>n>>m;
ll a[n];
for(ll i=0;i<n;i++)
{
cin>>a[i];
}
build(a,0,n-1,0);
/*for(ll i=0;i<2*n-1;i++)
{
cout<<i<<" : ";
for(ll j=0;j<seg[i].size();j++)
{
cout<<seg[i][j]<<" ";
}
cout<<endl;
}*/
while(m--)
{
cin>>x>>y>>k;
cout<<query(0,n-1,x-1,y-1,k,0,n)<<endl;
q.clear();
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgaW50IGxsOwojZGVmaW5lIE1BWCAxMDAwMDAxCnZlY3RvcjxsbD4gc2VnW01BWF07CnZlY3RvcjxsbD4gcTsKIAp2b2lkIGJ1aWxkKGxsIGFbXSxsbCBsb3csbGwgaGlnaCxsbCBwb3MpCnsKICBpZihsb3c9PWhpZ2gpCiAgewogICAgc2VnW3Bvc10ucHVzaF9iYWNrKGFbbG93XSk7CiAgICByZXR1cm47CiAgfQogIGxsIG1pZD0obG93K2hpZ2gpLzI7CiAgYnVpbGQoYSxsb3csbWlkLDIqcG9zKzEpOwogIGJ1aWxkKGEsbWlkKzEsaGlnaCwyKnBvcysyKTsKICBtZXJnZShzZWdbMipwb3MrMV0uYmVnaW4oKSxzZWdbMipwb3MrMV0uZW5kKCksc2VnWzIqcG9zKzJdLmJlZ2luKCksc2VnWzIqcG9zKzJdLmVuZCgpLGJhY2tfaW5zZXJ0ZXIoc2VnW3Bvc10pKTsKfQogCmxsIHF1ZXJ5KGxsIGxvdyxsbCBoaWdoLGxsIHFsb3csbGwgcWhpZ2gsbGwgdmFsLGxsIHBvcyxsbCBuKQp7CiAgaWYocWxvdz5oaWdofHxxaGlnaDxsb3cpCiAgewogICAgcmV0dXJuIDA7CiAgfQogIGlmKHFsb3c8PWxvdyYmcWhpZ2g+PWhpZ2gpCiAgewogICAgcS5pbnNlcnQocS5lbmQoKSxzZWdbcG9zXS5iZWdpbigpLHNlZ1twb3NdLmVuZCgpKTsKICAgIGlmKHFsb3c9PTAmJnFoaWdoPT1uLTEpCiAgICB7CiAgICAgIHJldHVybiBxW3ZhbC0xXTsKICAgIH0vL3VwcGVyX2JvdW5kKHNlZ1twb3NdLmJlZ2luKCksc2VnW3Bvc10uZW5kKCksdmFsKS1zZWdbcG9zXS5iZWdpbigpOwogICAgcmV0dXJuIDA7CiAgfQogIGxsIG1pZD0obG93K2hpZ2gpLzI7CiAgbGwgYT1xdWVyeShsb3csbWlkLHFsb3cscWhpZ2gsdmFsLDIqcG9zKzEsbik7CiAgbGwgYj1xdWVyeShtaWQrMSxoaWdoLHFsb3cscWhpZ2gsdmFsLDIqcG9zKzIsbik7CiAgLy9tZXJnZShzZWdbMipwb3MrMV0uYmVnaW4oKSxzZWdbMipwb3MrMV0uZW5kKCksc2VnWzIqcG9zKzJdLmJlZ2luKCksc2VnWzIqcG9zKzJdLmVuZCgpLGJhY2tfaW5zZXJ0ZXIocSkpOwogIC8qZm9yKGxsIGk9MDtpPHEuc2l6ZSgpO2krKykKICB7CiAgICBjb3V0PDxxW2ldPDwiICI7CiAgfQogIGNvdXQ8PGVuZGw7Ki8KICBzb3J0KHEuYmVnaW4oKSxxLmVuZCgpKTsKICByZXR1cm4gcVt2YWwtMV07Cn0KIAppbnQgbWFpbigpCnsKICBsbCBuLG0seCx5LGs7CiAgY2luPj5uPj5tOwogIGxsIGFbbl07CiAgZm9yKGxsIGk9MDtpPG47aSsrKQogIHsKICAgIGNpbj4+YVtpXTsKICB9CiAgYnVpbGQoYSwwLG4tMSwwKTsKICAvKmZvcihsbCBpPTA7aTwyKm4tMTtpKyspCiAgewogICAgY291dDw8aTw8IiA6ICI7CiAgICBmb3IobGwgaj0wO2o8c2VnW2ldLnNpemUoKTtqKyspCiAgICB7CiAgICAgIGNvdXQ8PHNlZ1tpXVtqXTw8IiAiOwogICAgfQogICAgY291dDw8ZW5kbDsKICB9Ki8KICB3aGlsZShtLS0pCiAgewogICAgY2luPj54Pj55Pj5rOwogICAgY291dDw8cXVlcnkoMCxuLTEseC0xLHktMSxrLDAsbik8PGVuZGw7CiAgICBxLmNsZWFyKCk7CiAgfQp9