311342: CF1971G. XOUR

G. XOURtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given an array $a$ consisting of $n$ nonnegative integers.

You can swap the elements at positions $i$ and $j$ if $a_i~\mathsf{XOR}~a_j < 4$, where $\mathsf{XOR}$ is the bitwise XOR operation.

Find the lexicographically smallest array that can be made with any number of swaps.

An array $x$ is lexicographically smaller than an array $y$ if in the first position where $x$ and $y$ differ, $x_i < y_i$.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2\cdot10^5$) — the length of the array.

The second line of each test case contains $n$ integers $a_i$ ($0 \leq a_i \leq 10^9$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output $n$ integers — the lexicographically smallest array that can be made with any number of swaps.

ExampleInput

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

Output

0 1 2 3 
1 5 2 6 7 
1 1 1 1 2 2 2 2 
16 4 1 64 

Note

For the first test case, you can swap any two elements, so we can produce the sorted array.

For the second test case, you can swap $2$ and $1$ (their $\mathsf{XOR}$ is $3$), $7$ and $5$ (their $\mathsf{XOR}$ is $2$), and $7$ and $6$ (their $\mathsf{XOR}$ is $1$) to get the lexicographically smallest array.

题目大意：
给定一个由非负整数组成的数组 $a$。如果 $a_i \oplus a_j < 4$，则可以交换位置 $i$ 和 $j$ 的元素，其中 $\oplus$ 是按位异或操作。求可以通过任意次数的交换得到的字典序最小的数组。数组 $x$ 在字典序上小于数组 $y$ 是指在 $x$ 和 $y$ 首次出现不同的位置上，$x_i < y_i$。

输入数据格式：
第一行包含一个整数 $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$ 个整数——可以通过任意次数的交换得到的字典序最小的数组。题目大意： 给定一个由非负整数组成的数组 $a$。如果 $a_i \oplus a_j < 4$，则可以交换位置 $i$ 和 $j$ 的元素，其中 $\oplus$ 是按位异或操作。求可以通过任意次数的交换得到的字典序最小的数组。数组 $x$ 在字典序上小于数组 $y$ 是指在 $x$ 和 $y$ 首次出现不同的位置上，$x_i < y_i$。 输入数据格式： 第一行包含一个整数 $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$ 个整数——可以通过任意次数的交换得到的字典序最小的数组。