题目描述
给定长度为 $n$ 的序列与 $q$ 次询问，每次询问区间 $[l,r]$ 中第 $k$ 小的数（相同数值按出现次数计）。请用主席树（可持久化线段树）等高效方法求解。
输入格式
第一行两个整数 $n,q$；第二行 $n$ 个整数 $a_i$；接下来 $q$ 行每行三个整数 $l,r,k$。
输出格式
每行一个整数，即该区间第 $k$ 小的原始数值。
数据范围
$$1 \le n,q \le 2\times 10^5,\ |a_i| \le 10^9$$
给定长度为 $n$ 的序列与 $q$ 次询问，每次询问区间 $[l,r]$ 中第 $k$ 小的数（相同数值按出现次数计）。请用主席树（可持久化线段树）等高效方法求解。
第一行两个整数 $n,q$；第二行 $n$ 个整数 $a_i$；接下来 $q$ 行每行三个整数 $l,r,k$。
每行一个整数，即该区间第 $k$ 小的原始数值。
5 3 3 1 4 1 5 2 2 4 1 5 2 2 1 5 4
5 1 5
3 3 -1 -1 -1 1 1 1 1 2 2 1 3 3
-1 -1 -1