题目内容

报文流水线里有一段长度为 $n$ 的排列 $s_1,s_2,\ldots,s_n$。系统会执行恰好 $t$ 次局部整理：

每次从左到右找到第一个满足 $s_i>s_{i+1}$ 的位置 $i$，交换 $s_i$ 与 $s_{i+1}$。

若不存在这样的位置，该次操作什么也不做。

请输出 $t$ 次操作后的排列。

输入描述

第一行一个整数 $q$（$1\le q\le 100$），表示询问个数。

每组询问：

• 第一行两个整数 $n,t$（$1\le n\le 1000$，$0\le t\le 1000000000$）；
• 第二行 $n$ 个互不相同的整数 $s_1,s_2,\ldots,s_n$（$1\le s_i\le n$）。

保证单个文件中所有询问的 $n$ 之和不超过 $1000$。

输出描述

对每个询问输出一行 $n$ 个整数，为操作结束后的排列。

样例1

输入

3
5 2
2 3 1 5 4
3 100
3 2 1
4 0
2 1 3 4

输出

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

说明

第 $1$ 个询问：$[2,3,1,5,4]\xrightarrow{i=2}[2,1,3,5,4]\xrightarrow{i=1}[1,2,3,5,4]$。

第 $2$ 个询问：逆序足够少，$t$ 很大时最终升序为 $1\ 2\ 3$。

第 $3$ 个询问：$t=0$，输出原排列。