题目描述

给定一个含有 $n$ 个数的序列 $a_1,a_2 \dots a_n$，执行 $m$ 次操作：

• l r k 表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数。

输入格式

第一行两个正整数 $n,m$，表示序列长度与操作个数。

第二行 $n$ 个整数，表示 $a_1,a_2 \dots a_n$。

接下来 $m$ 行，每行表示一个操作。

输出格式

对于每一次询问，输出一行一个整数表示答案。

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

5
6
3

数据范围/提示

对于 $100\%$ 的数据，$1\le n \le 10^5$，$1\le m\le 10^4$，$1 \le k \le r-l+1$，$|a_i| \le 10^9$。