The K-th Number

You want to build a function that sorts a range of an array and then returns the value at a given rank.

An array $a[1 \dots n]$ of size $n$ stores $n$ distinct integers. For this array, define the function $Q(i, j, k)$ as follows.

$Q(i, j, k)$: returns the $k$-th smallest value when the subarray $a[i \dots j]$ is sorted in ascending order.

For example, suppose $a = (1, 5, 2, 6, 3, 7, 4)$ and consider $Q(2, 5, 3)$. The subarray $a[2 \dots 5]$ is $(5, 2, 6, 3)$, which becomes $(2, 3, 5, 6)$ after sorting. The 3rd value in the sorted array is 5, so $Q(2, 5, 3) = 5$.

Given the array $a$ and several queries $Q(i, j, k)$, write a program that prints the return value of each query.

The first line contains the array size $n$ and the number of queries $m$, separated by a space. ($1 \le n \le 100{,}000$, $1 \le m \le 5{,}000$)

The second line contains the $n$ array elements in order. Each element is an integer whose absolute value does not exceed $10^9$, and all elements are distinct.

Each of the following $m$ lines contains the arguments $i$, $j$, $k$ of one query. ($1 \le i \le j \le n$, $1 \le k \le j - i + 1$)

For each query, print the return value of $Q(i, j, k)$, one per line.