A16747 | $Isamatdin and His Magic Wand!$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

伊萨马特丁有 $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

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

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

C++ 编辑器

输入

输出