Isamatdin 将 $$$n$$$ 玩具排成一排。第 $$$i$$$ 个玩具有一个整数 $$$a_i$$$。他想把它们分类,否则他妈妈会骂他。
然而,Isamatdin 从来不喜欢按顺序排列玩具,所以他的朋友 JahonaliX 给了他一根魔杖来帮助他。不幸的是,JahonaliX 在制作魔杖时犯了一个小错误。
但 Isamatdin 不能再等了,决定无论如何都要使用那根坏掉的魔杖。魔杖只能交换两个玩具,如果它们的整数有 不同奇偶校验 (一个是偶数,另一个是奇数)。换句话说,仅当 $$$a_i \bmod 2 \neq a_j \bmod 2$$$ 时,您才可以交换位置 $$$(i, j)$$$ 中的玩具,其中 $$$\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$$$ 整数 - 使用所描述的操作可以获得的按字典顺序排列的最小序列。
示例
输入复制
742 3 1 453 2 1 3 443 7 5 121000000000 231 3 552 5 3 1 742 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)$$$。
在第三个和第四个测试用例中,我们无法交换任何位置,因为所有玩具整数都具有相同的奇偶校验。