K-th Smallest Element in Subarray

You are given an array of N integers and Q queries. Each query requires you to find the k-th smallest element in a specific subarray. The subarray is defined by two indices l and r (1-indexed), meaning that only the elements from arr[l] to arr[r] should be considered.

For a query defined by (l, r, k), you need to sort the subarray arr[l, r] and output the element at position k after sorting. Formally, if the sorted subarray is denoted as S, you must output:

$ S[k-1] $

Note: The array indices are 1-indexed.

inputFormat

The first line contains two integers N and Q representing the number of elements in the array and the number of queries, respectively.

The second line contains N integers which represent the array.

Each of the next Q lines contains three integers l, r, and k representing a query to find the k-th smallest element in the subarray from index l to r (inclusive).

outputFormat

Output Q integers in a single line, separated by a space. Each integer is the answer corresponding to one query.

## sample

5 3
5 3 1 2 4
1 3 2
2 5 1
3 5 3

3 1 4

</p>