异或交换（XOUR）

时间限制：2s
空间限制：256MB

题目描述

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

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

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

对于两个不同的等长数组 $x$ 和 $y$，设 $i$ 是它们第一个不同的位置。如果 $x_i<y_i$，则称数组 $x$ 的字典序小于数组 $y$。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$，表示数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示数组的元素。

输出格式

对于每个测试用例，输出一行 $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$、$7$ 和 $5$、$7$ 和 $6$。这三对数的异或值依次为 $3$、$2$、$1$，从而得到所求数组。

数据范围

• 对于所有数据，满足 $1\le t\le 10^4$。
• 对于所有数据，满足 $1\le n\le 2\cdot10^5$。
• 对于所有数据，满足 $0\le a_i\le 10^9$。
• 所有测试组共同满足 $\sum n\le 2\cdot10^5$。