# 2918. K-th Number

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 $k$-th order statistics in the array segment.

That is, given an array $a[1\ldots n]$ of different integer numbers, your program must answer a series of questions $Q(i, j, k)$ in the form: “What would be the $k$-th number in $a[i\ldots j]$ segment, if this segment was sorted?”
For example, consider the array $a = (1, 5, 2, 6, 3, 7, 4)$. Let the question be $Q(2, 5, 3)$. The segment $a[2 \ldots 5]$ is $(5, 2, 6, 3)$. If we sort this segment, we get $(2, 3, 5, 6)$, the third number is $5$, and therefore the answer to the question is $5$.

### 输入格式

The first line of the input file contains $n$ — the size of the array, and $m$ — the number of questions to answer $(1 \le n \le 100~000, 1 \le m \le 5~000)$.

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

The following $m$ lines contain question descriptions, each description consists of three numbers: $i, j, k$ $(1 \leq i \le j \le n, 1 \le k \le j - i + 1) and represents the question$Q(i, j, k)\$.

### 输出格式

For each question output the answer to it — the $k$-th number in sorted $a[i\ldots j]$ segment.

### 样例

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

Output
5
6
3


16 人解决，21 人已尝试。

25 份提交通过，共有 69 份提交。

4.9 EMB 奖励。