题目背景

这是非常经典的可持久化权值线段树入门题 —— 静态区间第 $k$ 小。数据已加强，需使用可持久化权值线段树解决，同时注意常数优化。

题目描述

给定由 $n$ 个整数构成的序列 $a$，对于指定闭区间 $[l, r]$，查询该区间内的第 $k$ 小值。

输入格式

1. 第一行：两个整数 $n$（序列长度）和 $m$（查询个数）。

2. 第二行：$n$ 个整数，表示序列的第 $i$ 个元素 $a_i$。

3. 接下来 $m$ 行：每行三个整数 $l, r, k$，表示查询区间 $[l, r]$ 内的第 $k$ 小值。

输出格式

对于每次查询，输出一行一个整数，表示该区间第 $k$ 小值。

样例

5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

6405
15770
26287
25957
26287

提示

样例1解释

序列长度 $n = 5$，数列为 $\{25957, 6405, 15770, 26287, 26465\}$。

• 第一次查询 $[2, 2]$，第 1 小值为 $6405$。

• 第二次查询 $[3, 4]$，第 1 小值为 $15770$。

• 第三次查询 $[4, 5]$，第 1 小值为 $26287$。

• 第四次查询 $[1, 2]$，第 2 小值为 $25957$。

• 第五次查询 $[4, 4]$，第 1 小值为 $26287$。

数据范围

• 对于20% 数据：$1 \leq n, m \leq 10$。

• 对于50% 数据：$1 \leq n, m \leq 10^3$。

• 对于80% 数据：$1 \leq n, m \leq 10^5$。

• 对于100% 数据：$1 \leq n, m \leq 2\times10^5$，$0 \leq a_i \leq 10^9$，$1 \leq l \leq r \leq n$，$1 \leq k \leq r - l + 1$。