限时

2s

描述

注意： 酷暑获得了主角光环 鱼数量无限

注意： 是第k小

萌萌哒酷暑要去烤鱼了，他带了一个可以同时烤$n$条鱼的烤架以及一大包鱼。到了烤场以后，酷暑开始烤鱼了，但是太熏了，于是让你来烤。因为你很土豪，所以你找了个仆人。酷暑让你去帮他烤$q$条鱼，每次烤鱼他会告诉你一个范围$[l,r]$，你要把一条和$[l,r]$中的第$k$小的鱼一样大小的鱼拿给他吃。你马上把你的仆人传送到了你的身边，然后告诉他鱼的大小，让他帮你烤。烤完后仆人会自己去酷暑那要鱼（ 序列里的鱼不会被拿走 ），不用你操心，你只要告诉他鱼的大小就好。然而问题来了，究竟鱼的大小是多小呢？这个问题就交给了你。

输入格式

第一行两个数，$n$和$q$
第二行$n$个数，第$j$个数$g_j$表示第$j$个位置放的鱼的大小为$g_j$
接下来$q$行每行三个数$l,r,k$
所有数均为非负整数，任意两个相邻数以空格隔开

输出格式

输出至多$q$行，表示$[l,r]$中的第$k$小的鱼的大小。

输入样例

5 3
1 2 2 2 3
1 3 2
2 2 1
4 5 2

输出样例

2
2
3

数据范围

数据有梯度所以暴力有分。
1<=n<=100000 1<=q<=50000