G. XOUR
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$, состоящий из $$$n$$$ неотрицательных целых чисел.

Вы можете поменять местами элементы на позициях $$$i$$$ и $$$j$$$, если $$$a_i~\mathsf{XOR}~a_j < 4$$$, где $$$\mathsf{XOR}$$$ — это побитовая операция XOR.

Найдите лексикографически наименьший массив, который можно получить любым количеством обменов.

Массив $$$x$$$ лексикографически меньше массива $$$y$$$, если на первой позиции, где $$$x$$$ и $$$y$$$ отличаются, $$$x_i < y_i$$$.

Входные данные

Первая строка содержит одно целое число $$$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$$$ целых чисел — лексикографически наименьший массив, который можно получить любым количеством обменов.

Пример
Входные данные
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$$$), чтобы получить лексикографически наименьший массив.