该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师已经激活了游戏中角色的所有天赋，也已经强化完了所有天赋！

终于徐老师要成为游戏里的顶尖高手了！

结果游戏又新出了一个系统——天赋排列系统！

允许玩家以特定的方式将自己的天赋进行排列，并且会按照天赋的排列结果给角色增加战斗力

这个天赋排列系统的规则是这样的，首先会随机选出玩家的 $n$ 个天赋放入系统，第 $i$ 个选出的天赋编号为 $a_i$

然后系统会规定一个排列系数 $x$

每次玩家可以选定一个天赋 $a_i(1 \leq i \leq x)$

然后系统会自动交换 $a_i$ 和 $a_{i+1}$ 这两个天赋的位置，然后继续交换 $a_{i+1}$ 和 $a_{i+2}$ 这两个天赋的位置，直到交换 $a_{n-1}$ 和 $a_n$ 这两个天赋，一轮交换结束

由于徐老师是游戏的忠实玩家（毕竟一个破游戏那么复杂徐老师都还在坚持玩下去）

于是游戏给徐老师了一个福利——徐老师的操作次数是无限的！

现在徐老师已经进入了该系统，他想知道自己可以操作出的所有天赋排列方案中，字典序最小和最大的方案分别是什么，这样他才可以选择如何操作自己的天赋序列

输入格式

本题目采用多组测试数据，输入第一行包含一个整数 $T$ 表示测试数据数量

对于每组测试数据：

输入第一行包含两个整数 $n,x$ 表示天赋数量和排列系数

输入第二行包含 $n$ 个整数 $a_i$，表示被选进系统的天赋编号

输出格式

对于每组测试数据输出两行

输出第一行包含 $n$ 个整数，表示最小的天赋序列方案

输出第二行包含 $n$ 个整数，表示最大的天赋序列方案

数据范围

对于 $30\%$ 的数据：$1 \leq T \leq 10$，$1 \leq x \leq n \leq 9$，$a$ 中的元素不超过 $10$。

对于 $60\%$ 的数据：$1 \leq T \leq 10$，$1 \leq x \leq n \leq 2000$，$a$ 中的元素不超过 $10^5$。

对于 $100\%$ 的数据：$1 \leq T \leq 10$，$1 \leq x \leq n \leq 10^5$，$a$ 中的元素不超过 $10^7$。

样例输入

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

样例输出

7 9 8
9 8 7
2 2 2 4 5
5 4 2 2 2