ForeverBell不仅精通破译密码,更是我军的重要代码编写者(至于什么代码,自己想吧).战争的日子是无聊的,有一天,ForeverBell找到了treeboy,出了一个极其简单的问题:给定一段序列,找出这段数列中第k小的数. 为了照顾treeboy的超弱语文水平,ForeverBell极其耐心地解释了这个问题:给定一个整数数列num[1...n],序列中的每个数字都不相同.你需要回答一组格式为Q(i,j,k)的查询,表示"在num[i...j]中第k小的数是多少". 由于treeboy不仅语文差,而且代码能力巨弱,所以再次找到了你,请你编写一个程序,应对ForeverBell的询问.

第一行两个整数n,m.分别是数列的总长度和ForeverBell询问的次数. 1≤n≤100 000，1≤m≤5 000 第二行有n个数，代表数列的元素，所有数都不相同，而且不会超过10^9 。 接下来有m行，每行三个整数i、j、k，代表一次查询，i、j、k满足：1≤i≤j≤n， 1≤k≤j-i+1。

一共m行.第i行表示第i次询问的答案.

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

5
6
3

抗战系列