2918. K-th Number

单测试点时限: 2.0 秒

内存限制: 256 MB

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly -th order statistics in the array segment.

That is, given an array of different integer numbers, your program must answer a series of questions in the form: “What would be the -th number in segment, if this segment was sorted?”
For example, consider the array . Let the question be . The segment is . If we sort this segment, we get , the third number is , and therefore the answer to the question is .

输入

The first line of the input file contains — the size of the array, and — the number of questions to answer .

The second line contains different integer numbers not exceeding by their absolute values — the array for which the answers should be given.

The following lines contain question descriptions, each description consists of three numbers: Q(i, j, k)$.

输出

For each question output the answer to it — the -th number in sorted segment.

样例

Input
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
Output
5
6
3

15 人解决,20 已尝试。

23 份提交通过,共有 67 份提交。

8.6 EMB 奖励。

创建: 7 年,6 月前.

修改: 1 年,3 月前.

最后提交: 5 月前.

来源: Northeastern Europe 2004, Northern Subregion