Description

Xiao Ka has $n$ dogs. Because of different breeds and ages, each dog has a different beauty value. The beauty value is inversely related to how pretty a dog is (the lower the beauty value, the prettier). At mealtime, the dogs stand in a line in order, waiting for their owner to give them food.

But Jiajia is really lazy; he refuses to feed so many dogs. Each time, he only feeds the dog that is the $k$-th most beautiful among the $i$-th to the $j$-th dogs (how heartless!). Moreover, to ensure that no single dog is fed too many times, none of the intervals $[i, j]$ contains another.

Input Format

The first line contains two integers $n,m$, where $m$ is the number of times Jiajia feeds the dogs.

The second line contains $n$ integers, where the $i$-th dog's beauty value is $a_i$.

The next $m$ lines each contain $3$ integers $i,j,k$, asking for the beauty value of the dog that is the $k$-th most beautiful among the dogs from $i$ to $j$.

Output Format

$m$ lines, each containing one integer, which is the beauty value of the dog fed each time.

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

3
2

Hint

Constraints: $1\le n \le 3\times 10^5 ,1\le m \le5\times10^4,0\le a_i<2^{31}$，且 $a_i$ 互不相同。

Translated by ChatGPT 5