#include <stdio.h>
#include <malloc.h>
#include <iostream>
using namespace std;
int n;
int **a;
int **st;
int *size;
void fastscan(int &number){
//variable to indicate sign of input number
bool negative = false;
register int c;
number = 0;
// extract current character from buffer
c = getchar();
if (c=='-')
{
// number is negative
negative = true;
// extract the next character from the buffer
c = getchar();
}
// Keep on extracting characters if they are integers
// i.e ASCII Value lies from '0'(48) to '9' (57)
for (; (c>47 && c<58); c=getchar())
number = number *10 + c - 48;
// if scanned input has a negative sign, negate the
// value of the input number
if (negative)
number *= -1;
}
int binarySearch(int s,int e,int arr[],int val){
if(s < e){
int mid = s + (e-s)/2;
if(val >= arr[mid]){
return binarySearch(mid+1,e,arr,val);
}else{
return binarySearch(s,mid,arr,val);
}
}
return s;
}
int query(int s,int e,int qs,int qe,int i,int k){
if(s == e){
return st[i][0];
}
int l1 = size[2*i+1];
int upperBound = binarySearch(0,l1,st[2*i+1],qe);
int lowerBound = binarySearch(0,l1,st[2*i+1],qs-1);
int mid = s + (e-s)/2;
if(upperBound - lowerBound >= k){
return query(s,mid,qs,qe,2*i+1,k);
}else{
return query(mid+1,e,qs,qe,2*i+2,(k - (upperBound-lowerBound)));
}
}
void mergeST(int i){
int left = 2*i+1;
int right = 2*i+2;
int l1 = size[left];
int l2 = size[right];
st[i] = (int *)(malloc(sizeof(int)*(l1+l2)));
size[i] = l1 + l2;
int a = 0;
int b = 0;
int c = 0;
while(a<l1 && b<l2){
if(st[left][a] <= st[right][b]){
st[i][c++] = st[left][a++];
}else{
st[i][c++] = st[right][b++];
}
}
while(a<l1){
st[i][c++] = st[left][a++];
}
while(b<l2){
st[i][c++] = st[right][b++];
}
}
void constructST(int s, int e,int i){
if(e < s){
return ;
}
if(e == s){
st[i] = (int *)(malloc(sizeof(int)*1));
st[i][0] = a[e][1];
size[i] = 1;
return ;
}
int mid = s + (e-s)/2;
constructST(s,mid,2*i+1);
constructST(mid+1,e,2*i+2);
mergeST(i);
}
void merge(int s,int mid,int e){
int l1 = mid - s + 1;
int l2 = e - mid;
int ** l = (int **)(malloc(sizeof(int *)*l1));
for(int i=0;i<l1;i++){
l[i] = (int *)(malloc(sizeof(int)*2));
}
int ** r = (int **)(malloc(sizeof(int *)*l2));
for(int i=0;i<l2;i++){
r[i] = (int *)(malloc(sizeof(int)*2));
}
for(int i=0;i<l1;i++){
l[i][0] = a[s+i][0];
l[i][1] = a[s+i][1];
}
for(int i=0;i<l2;i++){
r[i][0] = a[mid+i+1][0];
r[i][1] = a[mid+i+1][1];
}
int i = 0;
int j = 0;
int k = s;
while(i<l1 && j<l2){
if(l[i][0] <= r[j][0]){
a[k][0] = l[i][0];
a[k++][1] = l[i++][1];
}else{
a[k][0] = r[j][0];
a[k++][1] = r[j++][1];
}
}
while(i<l1){
a[k][0] = l[i][0];
a[k++][1] = l[i++][1];
}
while(j<l2){
a[k][0] = r[j][0];
a[k++][1] = r[j++][1];
}
}
void mergeSort(int s,int e){
if(s < e){
int mid = s + (e-s)/2;
mergeSort(s,mid);
mergeSort(mid+1,e);
merge(s,mid,e);
}
}
int main(){
fastscan(n);
// scanf("%d",&n);
int m;
fastscan(m);
// scanf("%d",&m);
int *tmp = (int *)(malloc(sizeof(int)*n));
a = (int **)(malloc(sizeof(int *)*n));
for(int i=0;i<n;i++){
a[i] = (int *)(malloc(sizeof(int)*2));
}
for(int i=0;i<n;i++){
// scanf("%d",&a[i][0]);
fastscan(a[i][0]);
tmp[i] = a[i][0];
a[i][1] = i;
}
mergeSort(0,n-1);
st = (int **)(malloc(sizeof(int *)*263005));
size = (int *)(malloc(sizeof(int)*263005));
constructST(0,n-1,0);
/* for(int i=0;i<4*n;i++){
for(int j=0;j<size[i];j++){
printf("%d ",st[i][j]);
}
printf("\n");
}
*/ while(m-- > 0){
int l;
int r;
int k;
// scanf("%d",&l);
// scanf("%d",&r);
// scanf("%d",&k);
fastscan(l);
fastscan(r);
fastscan(k);
l--;
r--;
printf("%d\n",tmp[query(0,n-1,l,r,0,k)]);
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxtYWxsb2MuaD4KI2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG47CmludCAqKmE7CmludCAqKnN0OwppbnQgKnNpemU7Cgp2b2lkIGZhc3RzY2FuKGludCAmbnVtYmVyKXsKICAgIC8vdmFyaWFibGUgdG8gaW5kaWNhdGUgc2lnbiBvZiBpbnB1dCBudW1iZXIKICAgIGJvb2wgbmVnYXRpdmUgPSBmYWxzZTsKICAgIHJlZ2lzdGVyIGludCBjOwogCiAgICBudW1iZXIgPSAwOwogCiAgICAvLyBleHRyYWN0IGN1cnJlbnQgY2hhcmFjdGVyIGZyb20gYnVmZmVyCiAgICBjID0gZ2V0Y2hhcigpOwogICAgaWYgKGM9PSctJykKICAgIHsKICAgICAgICAvLyBudW1iZXIgaXMgbmVnYXRpdmUKICAgICAgICBuZWdhdGl2ZSA9IHRydWU7CiAKICAgICAgICAvLyBleHRyYWN0IHRoZSBuZXh0IGNoYXJhY3RlciBmcm9tIHRoZSBidWZmZXIKICAgICAgICBjID0gZ2V0Y2hhcigpOwogICAgfQogCiAgICAvLyBLZWVwIG9uIGV4dHJhY3RpbmcgY2hhcmFjdGVycyBpZiB0aGV5IGFyZSBpbnRlZ2VycwogICAgLy8gaS5lIEFTQ0lJIFZhbHVlIGxpZXMgZnJvbSAnMCcoNDgpIHRvICc5JyAoNTcpCiAgICBmb3IgKDsgKGM+NDcgJiYgYzw1OCk7IGM9Z2V0Y2hhcigpKQogICAgICAgIG51bWJlciA9IG51bWJlciAqMTAgKyBjIC0gNDg7CiAKICAgIC8vIGlmIHNjYW5uZWQgaW5wdXQgaGFzIGEgbmVnYXRpdmUgc2lnbiwgbmVnYXRlIHRoZQogICAgLy8gdmFsdWUgb2YgdGhlIGlucHV0IG51bWJlcgogICAgaWYgKG5lZ2F0aXZlKQogICAgICAgIG51bWJlciAqPSAtMTsKfQoKCmludCBiaW5hcnlTZWFyY2goaW50IHMsaW50IGUsaW50IGFycltdLGludCB2YWwpewoJaWYocyA8IGUpewoJCWludCBtaWQgPSBzICsgKGUtcykvMjsKCQlpZih2YWwgPj0gYXJyW21pZF0pewoJCQlyZXR1cm4gYmluYXJ5U2VhcmNoKG1pZCsxLGUsYXJyLHZhbCk7CgkJfWVsc2V7CgkJCXJldHVybiBiaW5hcnlTZWFyY2gocyxtaWQsYXJyLHZhbCk7CgkJfQoJfQoJcmV0dXJuIHM7Cn0KCmludCBxdWVyeShpbnQgcyxpbnQgZSxpbnQgcXMsaW50IHFlLGludCBpLGludCBrKXsKCWlmKHMgPT0gZSl7CgkJcmV0dXJuIHN0W2ldWzBdOwoJfQoJaW50IGwxID0gc2l6ZVsyKmkrMV07CglpbnQgdXBwZXJCb3VuZCA9IGJpbmFyeVNlYXJjaCgwLGwxLHN0WzIqaSsxXSxxZSk7CglpbnQgbG93ZXJCb3VuZCA9IGJpbmFyeVNlYXJjaCgwLGwxLHN0WzIqaSsxXSxxcy0xKTsKCWludCBtaWQgPSBzICsgKGUtcykvMjsKCWlmKHVwcGVyQm91bmQgLSBsb3dlckJvdW5kID49IGspewoJCXJldHVybiBxdWVyeShzLG1pZCxxcyxxZSwyKmkrMSxrKTsKCX1lbHNlewoJCXJldHVybiBxdWVyeShtaWQrMSxlLHFzLHFlLDIqaSsyLChrIC0gKHVwcGVyQm91bmQtbG93ZXJCb3VuZCkpKTsKCX0KfQoKdm9pZCBtZXJnZVNUKGludCBpKXsKCWludCBsZWZ0ID0gMippKzE7CglpbnQgcmlnaHQgPSAyKmkrMjsKCWludCBsMSA9IHNpemVbbGVmdF07CglpbnQgbDIgPSBzaXplW3JpZ2h0XTsKCXN0W2ldID0gKGludCAqKShtYWxsb2Moc2l6ZW9mKGludCkqKGwxK2wyKSkpOwoJc2l6ZVtpXSA9IGwxICsgbDI7CglpbnQgYSA9IDA7CglpbnQgYiA9IDA7CglpbnQgYyA9IDA7Cgl3aGlsZShhPGwxICYmIGI8bDIpewoJCWlmKHN0W2xlZnRdW2FdIDw9IHN0W3JpZ2h0XVtiXSl7CgkJCXN0W2ldW2MrK10gPSBzdFtsZWZ0XVthKytdOwoJCX1lbHNlewoJCQlzdFtpXVtjKytdID0gc3RbcmlnaHRdW2IrK107CgkJfQoJfQoJd2hpbGUoYTxsMSl7CgkJc3RbaV1bYysrXSA9IHN0W2xlZnRdW2ErK107Cgl9Cgl3aGlsZShiPGwyKXsKCQlzdFtpXVtjKytdID0gc3RbcmlnaHRdW2IrK107Cgl9Cn0KCnZvaWQgY29uc3RydWN0U1QoaW50IHMsIGludCBlLGludCBpKXsKCWlmKGUgPCBzKXsKCQlyZXR1cm4gOwoJfQoJaWYoZSA9PSBzKXsKCQlzdFtpXSA9IChpbnQgKikobWFsbG9jKHNpemVvZihpbnQpKjEpKTsKCQlzdFtpXVswXSA9IGFbZV1bMV07CgkJc2l6ZVtpXSA9IDE7CgkJcmV0dXJuIDsKCX0KCWludCBtaWQgPSBzICsgKGUtcykvMjsKCWNvbnN0cnVjdFNUKHMsbWlkLDIqaSsxKTsKCWNvbnN0cnVjdFNUKG1pZCsxLGUsMippKzIpOwoJbWVyZ2VTVChpKTsKfQoKdm9pZCBtZXJnZShpbnQgcyxpbnQgbWlkLGludCBlKXsKCWludCBsMSA9IG1pZCAtIHMgKyAxOwoJaW50IGwyID0gZSAtIG1pZDsKCWludCAqKiBsID0gKGludCAqKikobWFsbG9jKHNpemVvZihpbnQgKikqbDEpKTsKCWZvcihpbnQgaT0wO2k8bDE7aSsrKXsKCQlsW2ldID0gKGludCAqKShtYWxsb2Moc2l6ZW9mKGludCkqMikpOwoJfQoJaW50ICoqIHIgPSAoaW50ICoqKShtYWxsb2Moc2l6ZW9mKGludCAqKSpsMikpOwoJZm9yKGludCBpPTA7aTxsMjtpKyspewoJCXJbaV0gPSAoaW50ICopKG1hbGxvYyhzaXplb2YoaW50KSoyKSk7Cgl9Cglmb3IoaW50IGk9MDtpPGwxO2krKyl7CgkJbFtpXVswXSA9IGFbcytpXVswXTsKCQlsW2ldWzFdID0gYVtzK2ldWzFdOwoJfQoJZm9yKGludCBpPTA7aTxsMjtpKyspewoJCXJbaV1bMF0gPSBhW21pZCtpKzFdWzBdOwoJCXJbaV1bMV0gPSBhW21pZCtpKzFdWzFdOwoJfQoJaW50IGkgPSAwOwoJaW50IGogPSAwOwoJaW50IGsgPSBzOwoJd2hpbGUoaTxsMSAmJiBqPGwyKXsKCQlpZihsW2ldWzBdIDw9IHJbal1bMF0pewoJCQlhW2tdWzBdID0gbFtpXVswXTsKCQkJYVtrKytdWzFdID0gbFtpKytdWzFdOwoJCX1lbHNlewoJCQlhW2tdWzBdID0gcltqXVswXTsKCQkJYVtrKytdWzFdID0gcltqKytdWzFdOwoJCX0KCX0KCXdoaWxlKGk8bDEpewoJCWFba11bMF0gPSBsW2ldWzBdOwoJCWFbaysrXVsxXSA9IGxbaSsrXVsxXTsKCX0KCXdoaWxlKGo8bDIpewoJCWFba11bMF0gPSByW2pdWzBdOwoJCWFbaysrXVsxXSA9IHJbaisrXVsxXTsKCX0KfQoKdm9pZCBtZXJnZVNvcnQoaW50IHMsaW50IGUpewoJaWYocyA8IGUpewoJCWludCBtaWQgPSBzICsgKGUtcykvMjsKCQltZXJnZVNvcnQocyxtaWQpOwoJCW1lcmdlU29ydChtaWQrMSxlKTsKCQltZXJnZShzLG1pZCxlKTsKCX0KfQoKaW50IG1haW4oKXsKCWZhc3RzY2FuKG4pOwovLwlzY2FuZigiJWQiLCZuKTsKCWludCBtOwoJZmFzdHNjYW4obSk7Ci8vCXNjYW5mKCIlZCIsJm0pOwoJaW50ICp0bXAgPSAoaW50ICopKG1hbGxvYyhzaXplb2YoaW50KSpuKSk7CglhID0gKGludCAqKikobWFsbG9jKHNpemVvZihpbnQgKikqbikpOwoJZm9yKGludCBpPTA7aTxuO2krKyl7CgkJYVtpXSA9IChpbnQgKikobWFsbG9jKHNpemVvZihpbnQpKjIpKTsKCX0KCWZvcihpbnQgaT0wO2k8bjtpKyspewoJLy8Jc2NhbmYoIiVkIiwmYVtpXVswXSk7CgkJZmFzdHNjYW4oYVtpXVswXSk7CgkJdG1wW2ldID0gYVtpXVswXTsKCQlhW2ldWzFdID0gaTsKCX0KCW1lcmdlU29ydCgwLG4tMSk7CglzdCA9IChpbnQgKiopKG1hbGxvYyhzaXplb2YoaW50ICopKjI2MzAwNSkpOwoJc2l6ZSA9IChpbnQgKikobWFsbG9jKHNpemVvZihpbnQpKjI2MzAwNSkpOwoJY29uc3RydWN0U1QoMCxuLTEsMCk7Ci8qCWZvcihpbnQgaT0wO2k8NCpuO2krKyl7CgkJZm9yKGludCBqPTA7ajxzaXplW2ldO2orKyl7CgkJCXByaW50ZigiJWQgIixzdFtpXVtqXSk7CgkJfQoJCXByaW50ZigiXG4iKTsKCX0KKi8Jd2hpbGUobS0tID4gMCl7CgkJaW50IGw7IAoJCWludCByOwoJCWludCBrOwoJLy8Jc2NhbmYoIiVkIiwmbCk7CgkvLwlzY2FuZigiJWQiLCZyKTsKCS8vCXNjYW5mKCIlZCIsJmspOwoJCWZhc3RzY2FuKGwpOwoJCWZhc3RzY2FuKHIpOwoJCWZhc3RzY2FuKGspOwoJCWwtLTsKCQlyLS07CgkJcHJpbnRmKCIlZFxuIix0bXBbcXVlcnkoMCxuLTEsbCxyLDAsayldKTsKCX0KCXJldHVybiAwOwp9