1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define MID ((l+r)>>1) 6 using namespace std; 7  8 const int N=100500; 9 10 int a[N],s[N],t[20][N],num[20][N];11 int n,m;12 void build(int c,int l,int r){13     int lm=MID-l+1,lp=l,rp=MID+1;14     for(int i=l;i<=MID;i++)15         lm-=s[i]<s[MID];16     for(int i=l;i<=r;i++)17     {18         if(i==l)19             num[c][i]=0;20         else21             num[c][i]=num[c][i-1];22         if(t[c][i]==s[MID])23         {24             if(lm)25             {26                 lm--;27                 num[c][i]++;28                 t[c+1][lp++]=t[c][i];29             }30             else31                 t[c+1][rp++]=t[c][i];32         }33         else if(t[c][i]<s[MID])34         {35             num[c][i]++;36             t[c+1][lp++]=t[c][i];37         }38         else39             t[c+1][rp++]=t[c][i];40     }41     if(l<r)42         build(c+1,l,MID),build(c+1,MID+1,r);43 }44 int query(int c,int l,int r,int ql,int qr,int k){45     if(l==r){46         return t[c][l];47     }48     int s,ss;49     if(l==ql)50         s=0,ss=num[c][qr];51     else52         s=num[c][ql-1],ss=num[c][qr]-num[c][ql-1];53     if(k<=ss)54         return query(c+1,l,MID,l+s,l+s+ss-1,k);55     else56         return query(c+1,MID+1,r,MID+1+ql-l-s,MID+1+qr-l-s-ss,k-ss);57 }58 int main()59 {60     int T;61 62     int l,r,k;63     cin>>T;64     while(T--){65         scanf("%d%d",&n,&m);66         for(int i=1;i<=n;i++){67             scanf("%d",&a[i]);68             s[i]=t[0][i]=a[i];69         }70         sort(s+1,s+1+n);71         build(0,1,n);72         for(int i=0;i<m;i++){73             scanf("%d%d%d",&l,&r,&k);74             printf("%d\n",query(0,1,n,l,r,(k)));75         }76     }77     return 0;78 }