← 返回题目列表

Codeforces · 2167/C

C. Isamatdin 和他的魔杖!

中文机器翻译题面 查看原题

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$$$ 整数 - 使用所描述的操作可以获得的按字典顺序排列的最小序列。

示例

输入
复制

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)$$$。

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