给定一个数组 $$$a$$$,其中包含 $$$n$$$ 个非负整数。
如果 $$$a_i~\mathsf{XOR}~a_j < 4$$$,则可以交换位置 $$$i$$$ 和 $$$j$$$ 处的元素,其中 $$$\mathsf{XOR}$$$ 是按位异或运算。
找到可以通过任意数量的交换组成的字典顺序最小的数组。
如果在 $$$x$$$ 和 $$$y$$$ 不同的第一个位置,$$$x_i < y_i$$$,则数组 $$$x$$$ 按字典顺序小于数组 $$$y$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — 数组的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$) — 数组的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$n$$$ 整数 - 可以通过任意数量的交换生成的按字典顺序排列的最小数组。
示例
输入 #1
4 4 1 0 3 2 5 2 7 1 5 6 8 1 2 1 2 1 2 1 2 4 16 4 1 64
输出 #1
0 1 2 3 1 5 2 6 7 1 1 1 1 2 2 2 2 16 4 1 64
注意
对于第一个测试用例,您可以交换任意两个元素,这样我们就可以生成排序数组。
对于第二个测试用例,您可以交换 $$$2$$$ 和 $$$1$$$ (它们的 $$$\mathsf{XOR}$$$ 是 $$$3$$$)、$$$7$$$ 和 $$$5$$$ (它们的 $$$\mathsf{XOR}$$$ 是 $$$2$$$),以及 $$$7$$$ 和$$$6$$$ (它们的 $$$\mathsf{XOR}$$$ 是 $$$1$$$)以获得按字典顺序最小的数组。