**15 人解决**，20 已尝试。

**23 份提交通过**，共有 67 份提交。

**8.6** EMB 奖励。

**单测试点时限: **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 奖励。