Description:


您在数据结构部门为微硬公司工作。 您在关于键插入的上一个任务失败后,被要求写一个新的数据结构,以便能够在数组段中快速返回第k的数据。
也就是说,给定一个不同整数的数组a [1 ... n],你的程序必须回答一系列问题Q(i,j,k),形式为:“ [i ... j]段中第k小的数据?“
例如,考虑数组a =(1,5,2,6,3,7,4)。 问题是Q(2,5,3)。
a [2 ... 5]是(5,2,6,3)。 如果我们对这段数组进行排序,我们得到(2,3,5,6),第三个数字是5,因此问题的答案是5。

Input:


输入文件的第一行包含n ---数组的大小,m ---要回答的问题数(1 <= n <= 100 000,1 <= m <= 5 000)。
第二行包含n个不超过 \(10^9\) 的绝对值的整数,即应给出答案的数组。
以下m行包含问题描述,每个描述由三个数字组成:i,j和k(1 <= i <= j <= n,1 <= k <= j - i + 1) (i,j,k)。

Output:


对于每个问题输出它的答案---序列a [i ... j]中的第k个数。

Sample Input:


Sample Output:


题解:


一道主席树的模板题,实现起来十分简单。