MKTHNUMBER.cpp

//In the Name of Allah Most Gracious, Most Merciful//
/*If you want something you've never had, you have  to do something you never did.*/

#include<bits/stdc++.h>
using namespace std;


#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define M 100007
#define INF 1e9
#define INFL 1e18
#define PI acos(-1)
#define mp make_pair
#define fast_in_out ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define MaxN 100010


//const int fx[]= {+1,-1,+0,+0};
//const int fy[]= {+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move


vector<int>tree[MaxN*4];
int arr[MaxN];
int n;


void build(int node,int b,int e)
{
    if(b==e)
    {
      // cout<<arr[b]<<endl;
        tree[node]=vector<int>(1,arr[b]);
        return;
    }
    int mid=(b+e)/2;
    int left=node*2;
    int right=node*2+1;
    build(left,b,mid);
    build(right,mid+1,e);
    merge(tree[left].begin(),tree[left].end(),tree[right].begin(),tree[right].end(),back_inserter(tree[node]));
}

int query(int node,int b,int e,int i,int j,int val)
{
    if(i>e || j<b)
    {
        return 0;
    }
    if(b>=i && e<=j)
    {
        int ans=upper_bound(tree[node].begin(),tree[node].end(),val-1)-tree[node].begin();
        return ans;
    }
    int mid=(b+e)/2;
    int left=node*2;
    int right=node*2+1;
    return query(left,b,mid,i,j,val)+query(right,mid+1,e,i,j,val);
}
int main()
{
    fast_in_out;
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout)
    int q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    build(1,1,n);
    //cout<<tree[1].size()<<endl;
//    for(int i=0;i<14;i++)
//    {
//        for(int j=0;j<tree[i].size();j++)
//        {
//            cout<<tree[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    sort(arr+1,arr+n+1);
    while(q--)
    {

    int x,y,kth;
    cin>>x>>y>>kth;
    int high=n,low=1;
    int mid;
    int ans;
    while(high>=low)
    {
        mid=(high+low)/2;
        int pos=query(1,1,n,x,y,arr[mid]);
       cout<<arr[mid]<<" "<<pos<<endl;
        if(pos==kth)
        {
           // cout<<arr[mid]<<endl;
           // cout<<arr[high]<<endl;
           ans=mid;
            break;
        }
        else if(pos>kth)
        {
            high=mid-1;
        }
        else
        {
            low=mid+1;
        }
    }
    cout<<arr[ans-1]<<endl;

    }
    return 0;
}