题目描述

给定一个由 $n$ 个非负整数组成的数组 $a$。

你可以交换位置 $i$ 和 $j$ 上的元素，当且仅当 $a_i~\mathsf{XOR}~a_j < 4$，其中 $\mathsf{XOR}$ 表示按位异或运算。

请找出通过任意次数的合法交换后，能够得到的字典序最小的数组。

如果在第一个不同的位置 $x$ 和 $y$ 满足 $x_i < y_i$，则数组 $x$ 的字典序小于数组 $y$。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_i$（$0 \leq a_i \leq 10^9$），表示数组的元素。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 $n$ 个整数，表示通过任意次数的合法交换后能够得到的字典序最小的数组。

样例

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

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$），从而得到字典序最小的数组。

由 ChatGPT 4.1 翻译

来源

Codeforces 1971G，英文题名 XOUR。