CF2167C Isamatdin and His Magic Wand!

伊萨马特丁有 $n$ 个玩具排成一排。第 $i$ 个玩具上有一个整数 $a_i$。他想要把它们排好序，否则他妈妈会责备他。 但伊萨马特丁一直不喜欢把玩具排好，于是他的朋友 JahonaliX 给了他一根魔法棒来帮忙。不幸的是，JahonaliX 在制作魔法棒时犯了个小错误。 然而，伊萨马特丁已经等不及了，还是决定使用这根坏了的魔法棒。这根魔法棒只能交换两个整数奇偶性不同（一个是偶数，一个是奇数）的玩具。也就是说，只有当 $a_i \bmod 2 \neq a_j \bmod 2$ 时，才可以交换第 $i$ 个和第 $j$ 个玩具，其中 $\bmod$ 表示整数除法的余数。 现在，他想知道，使用这根坏魔法棒，他能得到的字典序最小的排列是什么。 *注：* 如果存在某个下标 $i$，对于任意 $j

每组测试数据包含多组用例。第一行为测试用例组数 $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$ 个整数，表示用上述操作能够得到的字典序最小的序列。

在第一个测试用例中，我们可以交换 $(1, 3)$ 位置，之后交换 $(2, 3)$ 位置。 在第二个测试用例中，我们可以依次交换 $(1, 2)$、$(1, 3)$，再交换 $(2, 3)$ 位置。 在第三和第四个测试用例中，所有玩具整数的奇偶性均相同，无法进行任何交换。 由 ChatGPT 5 翻译