题目描述

对于一个长度为 $m$ 的排列片段

$$B=(B_1,B_2,\ldots,B_m)，$$

你可以选择若干个分界点，将 $B$ 划分成若干个非空连续段，并要求每一段的长度都不超过 $K$。

随后，将每一段内部的元素分别按照从小到大的顺序排序，再按照这些段原本的先后顺序拼接，得到一个新的序列 $C$。

例如，当

$$B=(4,1,3,2,6),\qquad K=3$$

时，可以划分为

$$(4,1,3)\mid(2,6)，$$

分别排序并拼接后得到

$$C=(1,3,4,2,6)。$$

对于所有合法的划分方案，定义 $f(B)$ 为能够得到的、字典序最小的序列。

两个等长序列 $X,Y$ 的字典序比较方式如下：找到最小的下标 $i$ 使得 $X_i\ne Y_i$，若 $X_i<Y_i$，则称 $X$ 的字典序小于 $Y$。

现在给定一个长度为 $N$ 的排列

$$A=(A_1,A_2,\ldots,A_N)，$$

以及 $Q$ 次互相独立的询问。每次询问给定三个整数 $L,R,X$，令

$$B=(A_L,A_{L+1},\ldots,A_R)，$$

请你求出 $f(B)$ 中的第 $X$ 个元素。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行输入三个整数 $N,K,Q$；
• 第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$；
• 接下来 $Q$ 行，每行输入三个整数 $L,R,X$，表示一次询问。

输出格式

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

$$f(A_L,A_{L+1},\ldots,A_R)$$

中的第 $X$ 个元素。

样例 1 输入

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

样例 1 输出

1
2
3
3
2
6

样例 1 解释

考虑整个排列时，一种最优划分为

$$(4,1,3)\mid(2)\mid(6,5)\mid(7)，$$

排序后得到

$$f(A)=(1,3,4,2,5,6,7)。$$

因此第 $1$ 个元素为 $1$，第 $4$ 个元素为 $2$。

样例 2 输入

1
10 4 8
8 2 5 1 9 4 10 3 7 6
1 10 1
1 10 7
2 9 4
3 8 6
4 10 2
1 5 5
6 10 3
5 5 1

样例 2 输出

1
9
3
10
3
9
7
9

样例 3

见选手目录下的 sort/sort3.in 与 sort/sort3.ans。

该样例满足子任务 $1$ 的约束条件。

样例 4

见选手目录下的 sort/sort4.in 与 sort/sort4.ans。

该样例满足子任务 $2$ 的约束条件。

样例 5

见选手目录下的 sort/sort5.in 与 sort/sort5.ans。

该样例满足子任务 $3$ 的约束条件。

样例 6

见选手目录下的 sort/sort6.in 与 sort/sort6.ans。

该样例满足子任务 $4$ 的约束条件。

样例 7

见选手目录下的 sort/sort7.in 与 sort/sort7.ans。

该样例满足子任务 $5$ 的约束条件。

样例 8

见选手目录下的 sort/sort8.in 与 sort/sort8.ans。

该样例满足子任务 $6$ 的约束条件。

样例 9

见选手目录下的 sort/sort9.in 与 sort/sort9.ans。

该样例满足子任务 $7$ 的约束条件。

数据范围

对于每个测试点，均满足：

$$1\le T\le2\times10^5，\quad 1\le K\le N\le2\times10^5，\quad 1\le Q\le2\times10^5，\quad \sum N,\sum Q\le2\times10^5。$$

保证 $A$ 是一个 $1$ 到 $N$ 的排列，且每次询问满足 $1\le L\le R\le N$、$1\le X\le R-L+1$。

子任务编号	分值	约束条件
$1$	$10$	$\sum N\le8,\ \sum Q\le8$
$2$		$\sum N\le300,\ \sum Q\le300$
$3$	$8$	对每组测试数据均有 $K=1$
$4$	$12$	对每组测试数据均有 $K=N$
$5$	$16$	对每组测试数据均有 $K\le100$
$6$		$\sum N\le5000,\ \sum Q\le5000$
$7$	$28$	无额外限制

本题采用捆绑测试。每个子任务内的测试点必须全部通过，才能获得该子任务分数。