限时

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