描述

你正在Macrohard公司的数据结构部门工作。在上一个关于键插入的任务失败后，你被要求编写一个新的数据结构，能够快速返回数组区间中第$k$小的数。

具体来说，给定一个由不同整数组成的数组$a[1...n]$，你的程序需要回答一系列形式为$Q(i,j,k)$的查询：“如果将$a[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)$，第$3$个数是$5$，因此查询的答案是$5$。

输入

输入的第一行包含两个整数$n$（数组大小）和$m$（需要回答的查询数量），其中$1≤n≤100000，1≤m≤5000$。

第二行包含$n$个不同的整数，其绝对值不超过$10^ 9$ ——表示需要处理的数组。

接下来的m行每行描述一个查询，包含三个数字$i、j$和$k（1≤i≤j≤n，1≤k≤j−i+1）$，表示查询$Q(i,j,k)$。

输出

对于每个查询，输出其答案——排序后的$a[i...j]$区间中第$k$个数。

输入数据 1

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

输出数据 1

5
6
3

来源

2004年欧洲东北部，北部子区域