← 返回题目列表

Codeforces · 1971/G

G. 异或排序

中文机器翻译题面 查看原题

给定一个数组 $$$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$$$)以获得按字典顺序最小的数组。