Drunbee 非常喜欢狗狗，他有 n 只狗，每只狗都有一个忠诚度 val。午饭时间，n 只狗

会排成一行，编号 1~n。Drunbee 每次会选择一个区间，从区间中选择忠诚度第 k 小的狗喂

食，你能告诉他区间忠诚度第 k 小的狗的忠诚度是多少吗？ ★数据输入

输入第一行为两个正整数 n、m。表示有 n 只狗，m 次喂食。

接下来一行，有 n 个整数，依次是第一只狗的忠诚度，第二只狗的忠诚度，……，第 n 只狗的忠诚度。

接下来 m 行，每行三个整数 x,y,k，表示询问区间[x,y]的第 k 小的忠诚度是多少。

数据保证每次询问的区间可能会相交，但是任意两个不会相互包含，询问都合法。

n<=10^5，m<=5*10^4，val<=10^9 ★数据输出

对于每个询问，输出一行一个整数，表示所求的忠诚度。 输入示例 输出示例

7 2

1 5 2 6 3 7 4

2 7 3

1 5 3

4

3-Drunbee very fond of the dog, he n dogs, every dog ​ ​ has a loyalty val. The lunchtime, n dogs will line up, the No. 1 ~~ n. Drunbee each will select a range, from to choose loyalty k small dog interval feeding, you can tell he interval loyalty k small dog' s loyalty is how much you? ★ data input input behavior first two positive integers n, m. M times fed n dogs. The next line, n integer, followed by the first loyalty of dogs, dogs loyalty, ......, the dogs n loyalty. Next m rows, each three integers x, y, k, indicates the the inquired interval [x, y] of the k-th small loyalty. Data to ensure that each query interval may intersect, but any two not mutually inclusive asking are legitimate. n < = 10 ^ 5 m < = 5* 10 ^ 4 val < = 10 ^ 9 ★ data output for each inquiry line of output is an integer that indicates the demand loyalty. Enter the sample output of Example 7 2 1 5 2 6 3 7 4 2 7 3 1 5 3 4 3