该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

“区间第k小”是一个经典问题，使用划分树、主席树等多种数据结构均可完成，方法很多样，唯一的问题就是——

你不会写。

于是，善良的出题人决定通过卡空间来禁止啥都会写的dalao使用划分树和主席树。于是你可以自由发挥，用任何空间较小的方式解决这道题。

现在，给出长度为\(n\)的序列和\(m\)个询问，每次询问区间\([l, r]\)中第\(k\)小的数是多少。

时间限制2000ms，空间限制16M

输入描述

第一行两个整数\(n\)、\(m\)，表示序列长度和询问个数。
第二行\(n\)个整数，表示序列。
第三行开始每行一个询问，每行三个整数\(l\)、\(r\)、\(k\)，表示询问区间\([l, r]\)中第\(k\)小的数是多少。

输出描述

\(m\)行，每行一个整数，是每个询问的答案。

样例输入

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

样例输出

5
6
3

数据范围

\(n \le 500000\)
\(m \le 100000\)
所有数在int范围内。