题目描述

给定一长度为 $n$ 的 整数数组 $a$，一个整数 $k$，请输出数组中给定区间的第 $k$ 大的数是多少？

第 $k$ 大的数是指从大到小排序后第 $k$ 位置的数。

输入格式

第一行有两个整数 $n$ 和 $Q$，接下来的一行有 $n$ 个空格隔开的整数。接下来 $Q$ 行， 每行三个整数 $L,R,k$，表示求在原数组 $a$ 的区间 $[L,R]$ 中第 $k$ 大的数。 你不能改变 $a$ 中的各数的顺序。

输出格式

$Q$ 行，每行一个整数表示答案。

样例

6 1
1 2 3 4 5 6
1 6 1

6

数据规模

$ 1 < n \le 10^5,1 \le L \le R \le n, 1 \le Q \le 10^3, |a_i| \le 10^9$