20 人解决，28 人已尝试。
31 份提交通过，共有 131 份提交。
5.2 EMB 奖励。
单点时限: 2.0 sec
内存限制: 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 $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.
7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3
5 6 3
20 人解决，28 人已尝试。
31 份提交通过，共有 131 份提交。
5.2 EMB 奖励。