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

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

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

样例解释：


n=5，数列长度为 5，数列从第一项开始依次为 {25957,6405,15770,26287,26465}。

• 第一次查询为 [2,2] 区间内的第一小值，即为 6405。
• 第二次查询为 [3,4] 区间内的第一小值，即为 15770。
• 第三次查询为 [4,5] 区间内的第一小值，即为 26287。
• 第四次查询为 [1,2] 区间内的第二小值，即为 25957。
• 第五次查询为 [4,4] 区间内的第一小值，即为 26287。

数据规模与约定

• 对于 20% 的数据，满足 1≤n,m≤10。
• 对于 50% 的数据，满足 1≤n,m≤10³。
• 对于 80% 的数据，满足 1≤n,m≤10⁵。
• 对于 100% 的数据，满足 1≤n,m≤2×10⁵， ∣ai∣≤10⁹， 1≤l≤r≤n， 1≤k≤r−l+1。

整体二分 数据结构 树状数组 线段树