CF2167C.Isamatdin and His Magic Wand!

Isamatdin has $n$ toys arranged in a row. The $i$-th toy has an integer $a_i$. He wanted to sort them because otherwise, his mother would scold him.

However, Isamatdin never liked arranging toys in order, so his friend JahonaliX gave him a magic wand to help. Unfortunately, JahonaliX made a small mistake while creating the wand.

But Isamatdin couldn't wait any longer and decided to use the broken wand anyway. The wand can only swap two toys if their integers have different parity (one is even, the other is odd). In other words, you can swap toys in positions $(i, j)$ only if $a_i \bmod 2 \neq a_j \bmod 2$, where $\bmod$ — is the remainder of integer division.

Now he wants to know the lexicographically smallest$^{\text{∗}}$ arrangement he can achieve using this broken wand.

$^{\text{∗}}$A sequence $p$ is lexicographically smaller than a sequence $q$ if there exists an index $i$ such that $p_j = q_j$ for all $j \lt i$, and $p_i \lt q_i$.

伊萨马特丁有 $n$ 个玩具排成一排。第 $i$ 个玩具上标有一个整数 $a_i$。他想把这些玩具按顺序排列，否则他的妈妈会责骂他。

然而，伊萨马特丁向来不喜欢按顺序整理玩具，于是他的朋友贾洪阿里克斯送给他一根魔法棒来帮忙。不幸的是，贾洪阿里克斯在制作这根魔法棒时犯了一个小错误。

但伊萨马特丁已等不及了，决定无论如何都要使用这根损坏的魔法棒。该魔法棒仅允许交换两个整数奇偶性不同的玩具（即一个为偶数，另一个为奇数）。换言之，你只能在位置 $(i, j)$ 处交换玩具，当且仅当 $a_i \bmod 2 \neq a_j \bmod 2$，其中 $\bmod$ 表示整数除法的余数。

现在，他想知道利用这根损坏的魔法棒所能得到的字典序最小$^{\text{∗}}$ 的排列。

$^{\text{∗}}$ 序列 $p$ 比序列 $q$ 字典序更小，当且仅当存在某个下标 $i$，使得对所有 $j \lt i$ 都有 $p_j = q_j$，且 $p_i \lt q_i$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of toys.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the integers of the toys.

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output $n$ integers — the lexicographically smallest sequence that can be obtained using the described operation.

对于每个测试用例，输出 $n$ 个整数——即通过执行上述操作所能得到的字典序最小的序列。

In the first test case, we can swap positions $(1, 3)$ and then $(2, 3)$.

In the second test case, we can swap positions $(1, 2)$, $(1, 3)$, and then $(2, 3)$.

In the third and fourth test cases, we can't swap any positions because all toy integers have the same parity.

在第一个测试用例中，我们可以交换位置 $(1, 3)$，然后交换位置 $(2, 3)$。

在第二个测试用例中，我们可以依次交换位置 $(1, 2)$、$(1, 3)$ 和 $(2, 3)$。

在第三和第四个测试用例中，我们无法交换任何位置，因为所有玩具整数的奇偶性均相同。