2918. K-th Number

单点时限: 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.

样例

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

16 人解决,23 人已尝试。

25 份提交通过,共有 72 份提交。

5.2 EMB 奖励。

创建: 9 年,1 月前.

修改: 2 年,10 月前.

最后提交: 3 月,2 周前.

来源: Northeastern Europe 2004, Northern Subregion

题目标签