Range K-th Query

Given a sequence of \( n \) integers \( a \), you are asked to answer \( q \) queries. Each query is given by three integers \( l \), \( r \), and \( k \) and requires you to find the \( k \)-th smallest element in the subarray \( a[l\ldots r] \) (i.e., the closed interval from index \( l \) to \( r \)).

Note: The \( k \)-th smallest element is defined based on 1-indexed ordering after sorting the subarray in non-decreasing order.

Input Format: The first line contains two integers \( n \) and \( q \). The second line contains \( n \) integers representing the array \( a \). The following \( q \) lines each contain three integers \( l \), \( r \), and \( k \).

inputFormat

The first line contains two space-separated integers \( n \) and \( q \), where \( n \) is the number of elements in the array and \( q \) is the number of queries.

The second line contains \( n \) space-separated integers representing the array \( a \).

Each of the following \( q \) lines contains three space-separated integers \( l \), \( r \), and \( k \).

outputFormat

For each query, print the \( k \)-th smallest element in the subarray \( a[l\ldots r] \) on a new line.

sample

5 2
1 5 2 6 3
2 5 3
1 3 2

5
2