3320 - 任意区间的k大值

给定n个整数构成的序列a,将对于指定的闭区间[l, r]查询其区间内的第k小值。

输入

第一行包含两个整数,分别表示序列的长度n和查询的个数m。
第二行包含n个整数,第i个整数表示序列的第i个元素ai。
接下来m行每行包含三个整数l,r,k,表示查询区间[l, r]内的第k小值。

输出

对于每次询问,输出一行一个整数表示答案。

样例

输入

5 5
25957 6405 15770 26287 26465 
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

输出

6405
15770
26287
25957
26287

提示

对于100%的数据,满足1<=n,m<=2*10^5,|ai|<=10^9,1<=l<=r<=n,1<=k<=r-l+1。

时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题