C. Исаматдин и его волшебная палочка!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Исаматдина есть $$$n$$$ игрушек, выстроенных в ряд. У $$$i$$$-й игрушки есть число $$$a_i$$$. Он хотел их отсортировать, иначе мама его отругает.

Однако Исаматдин никогда не любил расставлять игрушки по порядку, поэтому его друг JahonaliX дал ему волшебную палочку, чтобы помочь. К сожалению, JahonaliX допустил небольшую ошибку при создании палочки.

Но Исаматдин не мог больше ждать и решил использовать сломанную палочку всё равно. Эта палочка может менять местами только две игрушки, если их числа имеют разную чётность (одно чётное, другое нечётное). Другими словами, вы можете поменять местами игрушки в позициях $$$(i, j)$$$ только если $$$a_i \bmod 2 \neq a_j \bmod 2$$$, где $$$\bmod$$$ — остаток от целочисленного деления.

Теперь он хочет узнать лексикографически минимальное$$$^{\text{∗}}$$$ расположение, которое он может получить, используя эту сломанную палочку.

$$$^{\text{∗}}$$$Последовательность $$$p$$$ лексикографически меньше последовательности $$$q$$$, если существует индекс $$$i$$$ такой, что $$$p_j = q_j$$$ для всех $$$j \lt i$$$, и $$$p_i \lt q_i$$$.

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество игрушек.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — числа на игрушках.

Гарантируется, что сумма всех $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел — лексикографически минимальную последовательность, которую можно получить, используя описанную операцию.

Пример
Входные данные
7
4
2 3 1 4
5
3 2 1 3 4
4
3 7 5 1
2
1000000000 2
3
1 3 5
5
2 5 3 1 7
4
2 4 8 6
Выходные данные
1 2 3 4 
1 2 3 3 4 
3 7 5 1 
1000000000 2 
1 3 5 
1 2 3 5 7 
2 4 8 6
Примечание

В первом примере можно поменять местами позиции $$$(1, 3)$$$, а затем $$$(2, 3)$$$.

Во втором примере можно поменять местами позиции $$$(1, 2)$$$, затем $$$(1, 3)$$$, а потом $$$(2, 3)$$$.

В третьем и четвёртом примерах нельзя поменять местами никакие позиции, поскольку все номера игрушек имеют одинаковую чётность.