SP3946 MKTHNUM - K-th Number

题目大意： 给你 $n$ 个数，多次询问某段区间中第 $k$ 小的数。

第一行有两个整数 $n,m$，分别为整数个数、询问次数。 第二行有 $n$ 个整数，其中第 $i$ 个为 $a_i$。 接下来 $m$ 行，每行三个整数 $i,j,k$，询问第 $i$ 个数到第 $j$ 个数中第 $k$ 小的数。

输出共 $m$ 行，为对每次询问的回答。

$1\le n \le 100000$ , $1 \le m \le 5000$ , $-10^9 \le a_i \le 10^9$。 ~~注意：简单的做法可是过不了的。~~ 感谢 @gjc1124646822 提供的翻译。 Fixed by @AnEasySong