K-th Number

You are working for Macrohard company in the data structures department. After failing your previous task about key insertion, you have been asked to write a new data structure that can efficiently answer $k$-th order statistic queries on segments of an array.

Given an array a_1, a_2, \dots, a_n consisting of $n$ different integers, your program must answer several queries Q(i, j, k): "What would be the $k$-th smallest number in the segment a_i, a_{i+1}, \dots, a_j if this segment was sorted?"

For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the query be Q(2, 5, 3). The segment a_2, a_3, a_4, a_5 is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), and the third smallest number is $5$, so the answer to this query is $5$.

\InputFileThe first line contains two integers $n$ and $m$ (1 \le n \le 100\,000, 1 \le m \le 5\,000): the size of the array and the number of queries, respectively.

The second line contains $n$ distinct integers a_1, a_2, \dots, a_n with absolute value not exceeding 10^9.

Each of the next $m$ lines contains three integers $i$, $j$, and $k$ (1 \le i \le j \le n, 1 \le k \le j-i+1), describing a query Q(i, j, k).

\OutputFileFor each query, output the answer: the $k$-th smallest number in the sorted segment a_i, \dots, a_j.