题目描述

给定一个长度为 $N$ 的序列 $v$，其中所有元素都是正整数，元素之间不一定互不相同。

你可以进行如下操作：

• 选择两个相邻位置上的元素，并交换它们。

给定一个自然数 $K$，请你求出在进行至多 $K$ 次相邻交换后，能够得到的字典序最小的序列。

输入格式

第一行包含一个整数 $T$，表示测试组数。

接下来依次给出 $T$ 组测试数据。每组测试数据包含两行：

第一行包含两个整数 $N,K$。

第二行包含 $N$ 个整数，表示序列 $v_1,v_2,\ldots,v_N$。

输出格式

对于每组测试数据，输出一行，包含 $N$ 个整数，表示在原序列基础上进行至多 $K$ 次相邻交换后能得到的字典序最小序列。

数据范围与约定

• $1\le N\le 250000$；
• $T\le 2500$；
• 一个输入文件中，所有测试组的 $N$ 之和不超过 $250000$；
• $1\le K\le \dfrac{N(N-1)}2$；
• $1\le v_i\le N$；
• 注意：$K$ 可能较大，需要使用 64 位整数读入。
• 对某个测试文件计分时，需要该文件内所有测试组都回答正确。

字典序定义如下：序列 $a_1,a_2,\ldots,a_n$ 比序列 $b_1,b_2,\ldots,b_n$ 字典序更小，当且仅当存在一个位置 $P$，满足：

$$a_1=b_1,a_2=b_2,\ldots,a_{P-1}=b_{P-1},\qquad a_P<b_P.$$

子任务

子任务	分值	限制
1	5	$K=\dfrac{N(N-1)}2$
2	7	$K=1$
3	23	$T\le 10,\ N\le 50$
4		$T\le 10,\ N\le 100$
5	12	$T\le 10,\ N\le 500$
6	24	$T\le 10,\ N\le 2000$
7	25	无额外限制

样例

输入

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

输出

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

样例解释

对于第一组测试数据，序列为：

$$(4,2,3,1,1).$$

最多可以进行 $K=2$ 次相邻交换。

先交换 $v_1$ 和 $v_2$，得到：

$$(2,4,3,1,1).$$

再交换当前第 $2$ 个和第 $3$ 个元素，得到：

$$(2,3,4,1,1).$$

这是在至多两次相邻交换后可以得到的字典序最小序列。