Вам дан массив \(a\), состоящий из \(n\) неотрицательных целых чисел.
Вы можете поменять местами элементы на позициях \(i\) и \(j\), если \(a_i~\mathsf{XOR}~a_j < 4\), где \(\mathsf{XOR}\) — это побитовая операция XOR.
Найдите лексикографически наименьший массив, который можно получить любым количеством обменов.
Массив \(x\) лексикографически меньше массива \(y\), если на первой позиции, где \(x\) и \(y\) отличаются, \(x_i < y_i\).
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел — лексикографически наименьший массив, который можно получить любым количеством обменов.
Примечание
В первом примере вы можете поменять местами любые два элемента, поэтому мы можем получить отсортированный массив.
Во втором примере вы можете поменять местами \(2\) и \(1\) (их \(\mathsf{XOR}\) равен \(3\)), \(7\) и \(5\) (их \(\mathsf{XOR}\) равен \(2\)), и \(7\) и \(6\) (их \(\mathsf{XOR}\) равен \(1\)), чтобы получить лексикографически наименьший массив.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
0 1 2 3
1 5 2 6 7
1 1 1 1 2 2 2 2
16 4 1 64
|