kth sorted element by per seg tree

int arr[MAX],pk[MAX];

struct node{
    node *left,*right;
    int sum;
    node(){
        sum = 0;
        left = right = NULL;
    }
}*root[MAX];

node* Build(int b,int e){
    if(b==e){
        node *ret = new node();
        ret->sum = 0;
        return ret;
    }
    int mid = (b+e)>>1;
    node *ret = new node();
    ret->left = Build(b,mid);
    ret->right = Build(mid+1,e);
    ret->sum = ret->left->sum + ret->right->sum;
    return ret;
}

node *update(node *ptr,int b,int e,int indx,int val){

    if(b>indx||indx>e)return ptr;
    if(b==e){
        node *ret = new node();
        ret->sum =  val;
        return ret;
    }
    int mid = (b+e)>>1;
    node *ret = new node();
    ret->left = update(ptr->left,b,mid,indx,val);
    ret->right = update(ptr->right,mid+1,e,indx,val);
    ret->sum = ret->left->sum + ret->right->sum;
    return ret;
}


int query(node *l,node *r,int b,int e,int k){
    if(b==e)return b;
    int mid = (b+e)>>1;
    ///cout<<b<<" "<<e<<" "<< r->left->sum<<" "<<l->left->sum<<endl;
    int cnt = r->left->sum - l->left->sum;
    if(cnt>=k)return query(l->left,r->left,b,mid,k);
    else return query(l->right,r->right,mid+1,e,k-cnt);

}


int main()
{
    ///booster()
    ///read("input.txt");

    int n,q;
    scani(n);
    scani(q);
    vi v;
    map<int,int>m;
    for(int i = 0;i<n;i++){
        scani(arr[i]);
        v.pb(arr[i]);
    }
    sort(all(v));
    for(int i = 0;i<v.size();i++){
        m[v[i]] = i+1;
        pk[i+1] = v[i];
    }
    root[0] = Build(1,n);
    for(int i = 0;i<n;i++){
        root[i+1] = update(root[i],1,n,m[arr[i]],1);
    }

    while(q--){
        int l,r,k;
        scani3(l,r,k);
        OUT(pk[query(root[l-1],root[r],1,n,k)]);
    }



    return 0;
}