Find Kth smallest element in a subarray

---

Problem statement

You are given an Array of size N and your task is to find the Kth smallest element in a subarray of given range i to r (both inclusive) There can be multiple queries.

Input format

First line of input will be two space separated integers N and Q, the size of array and number of queries respectively. Following line will have N space separated integers, they will contain the elements of array. Then, there will be Q number of lines with i, r and k separated by space. Here i is the start index and r is the end index inside which you have to find the kth smallest element of array.

Output format

output Q lines telling the kth smallest number in the given range i and r both inclusive.

Constraints

There will be multiple queries. 1 <= k <= r-i+1

Sample Input 1

7 2
3 2 5 4 7 1 9
2 6 3
1 5 2

Sample output 1

4
2

Explanation

Here 3rd smallest element in range 2 to 6 is 4 so output that, similarly, in range 1 to 5 the 2nd smallest element in 2 so we output that.

---

• Solve
• Read editiorial

Running Your code....