Feeding the k-th Most Beautiful Dog

There are $n$ dogs with unique beauty values in Xiao Ka's home. The beauty value is inversely proportional to the attractiveness (i.e. the lower the beauty value, the more beautiful the dog). When it’s time to eat, the dogs line up in order. However, because Jia Jia is very lazy, he only feeds one dog per session. In each session, he selects a consecutive segment of dogs from position $i$ to $j$ (inclusive) and feeds only the $k$-th most beautiful dog in that segment (i.e., the one with the $k$-th smallest beauty value). Furthermore, to ensure that no dog is fed too many times, the chosen feeding intervals $[i,j]$ will never contain one another.

Given the initial ordering of dogs and a series of feeding queries, your task is to determine which dog gets fed in each query.

inputFormat

The first line contains two integers $n$ and $m$, representing the number of dogs and the number of feeding queries, respectively.

The second line contains $n$ integers, where the $i$-th integer represents the beauty value of the $i$-th dog (all values are unique). Note that a lower beauty value indicates a more beautiful dog.

Each of the next $m$ lines contains three integers $i$, $j$, and $k$, representing a query. For this query, consider the segment of dogs from the $i$-th to the $j$-th dog (inclusive) and output the beauty value of the $k$-th most beautiful dog in this segment (i.e. the $k$-th smallest number in that segment).

outputFormat

For each query, output a single line containing the beauty value of the selected dog.

sample

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

3
1
5