题目描述

伊萨马特丁有 $n$ 个玩具排成一排。第 $i$ 个玩具上有一个整数 $a_i$。他想要把它们排好序，否则他妈妈会责备他。

但伊萨马特丁一直不喜欢把玩具排好，于是他的朋友 JahonaliX 给了他一根魔法棒来帮忙。不幸的是，JahonaliX 在制作魔法棒时犯了个小错误。

然而，伊萨马特丁已经等不及了，还是决定使用这根坏了的魔法棒。这根魔法棒只能交换两个整数奇偶性不同（一个是偶数，一个是奇数）的玩具。也就是说，只有当 $a_i \bmod 2 \neq a_j \bmod 2$ 时，才可以交换第 $i$ 个和第 $j$ 个玩具，其中 $\bmod$ 表示整数除法的余数。

现在，他想知道，使用这根坏魔法棒，他能得到的字典序最小的排列是什么。

注： 如果存在某个下标 $i$，对于任意 $j<i$ 均有 $p_j=q_j$，且 $p_i<q_i$，则序列 $p$ 的字典序小于序列 $q$。

输入格式

每组测试数据包含多组用例。第一行为测试用例组数 $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 翻译

样例

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