1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 #include<cstring> 7 #define PAU putchar(' ') 8 #define ENT putchar(' ') 9 #define lson x?x->ch[0]:x,y->ch[0],L,M 10 #define rson x?x->ch[1]:x,y->ch[1],M+1,R 11 using namespace std; 12 const int maxn=10000+10,inf=-1u>>1,maxnode=200000+10; 13 struct node{node*ch[2];int siz;node(){siz=0;}}fol[maxnode],*root[maxn],*nodecnt=fol; 14 node*ls(node*x){return x?x->ch[0]:x;} 15 node*rs(node*x){return x?x->ch[1]:x;} 16 int sz(node*x){return x?x->siz:0;} 17 int n,Q,A[maxn],num[maxn]; 18 void build(node*x,node*&y,int L,int R,int pos){ 19 y=nodecnt++;y->siz=sz(x)+1;if(L==R)return;int M=L+R>>1; 20 if(pos<=M) y->ch[1]=rs(x),build(lson,pos); 21 else y->ch[0]=ls(x),build(rson,pos); 22 } 23 int query(node*x,node*&y,int L,int R,int k){ 24 if(L==R)return L;int M=L+R>>1,kth=sz(ls(y))-sz(ls(x)); 25 if(k<=kth) return query(lson,k);return query(rson,k-kth); 26 } 27 int find(int v){ 28 int L=1,R=n,M;while(L<R){M=L+R>>1;if(num[M]<v)L=M+1;else R=M;}return L; 29 } 30 inline int read(){ 31 int x=0,sig=1;char ch=getchar(); 32 while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();} 33 while(isdigit(ch)) x=10*x+ch-'0',ch=getchar(); 34 return x*=sig; 35 } 36 inline void write(int x){ 37 if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x; 38 int len=0,buf[15];while(x) buf[len++]=x%10,x/=10; 39 for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return; 40 } 41 void init(){ 42 n=read();Q=read();for(int i=1;i<=n;i++)num[i]=A[i]=read(); 43 sort(num+1,num+1+n);for(int i=1;i<=n;i++)build(root[i-1],root[i],1,n,find(A[i])); 44 return; 45 } 46 void work(){ 47 int a,b,c; 48 while(Q--){ 49 a=read();b=read();c=read(); 50 write(num[query(root[a-1],root[b],1,n,c)]);ENT; 51 } 52 return; 53 } 54 void print(){ 55 return; 56 } 57 int main(){ 58 init();work();print();return 0; 59 }