时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给定一个长度为 \(n\) 的整数序列：\(A[1]、A[2]、…、A[n](0≤A[i]≤1000000)\)。

　　再给出 \(m\) 个查询：\(i\ j\ k\) 表示查询当前序列的连续子序列 \(A[i]..A[j]\) 中第 \(k\) 小的元素（把 \(A[i]..A[j]\) 由小到大排序后的第 \(k\) 个元素）。

【输入格式】

　　第一行包含两个整数 \(n\) 和 \(m\)，表示数组有 \(n\) 个元素，\(m\) 表示有 \(m\) 个查询操作；接下来的一行包含 \(n\) 个整数，第 \(i\) 个整数表示 \(A[i]\)；再接下来的 \(m\) 行，每行表示一个查询：\(i\ j\ k(1≤i≤j≤n, 1≤k≤j-i+1)\)。

【输出格式】

　　对于每个查询，输出查询结果。

【输入输出样例】

　Input

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

　Output

5
6
3

【数据限制】

　　对于 \(30\%\) 的数据，\(0<n≤100\)，\(0<m≤100\)
　　对于 \(60\%\) 的数据，\(0<n≤5000\)，\(0<m≤10000\)
　　对于 \(100\%\) 的数据，\(0<n≤100000\)，\(0<m≤100000\)

【来源】

　　Mr.he**