该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

实验室有 $n$ 个样本排成一列。第 $i$ 个样本的测量值为正整数 $a_i$。为便于分析，需要将样本按测量值升序排列。

实验室有一台自动交换装置，但该装置存在故障：只能交换两个测量值奇偶性不同的样本。即只能交换满足 $a_i mod 2 ≠ a_j mod 2$ 的位置 $i$ 和 $j$ 上的样本。

研究人员希望在遵守此限制的前提下，通过若干次交换使样本序列的字典序最小。请输出能够获得的最小字典序排列。

• 字典序定义： 序列 $p$ 字典序小于序列 $q$，当存在下标 $i$ 使得对所有 $j < i$ 有 $p_j = q_j$，且 $p_i < q_i$。

输入格式

第一行包含整数 $t（1 ≤ t ≤ 10^4）$——测试用例数。 每个测试用例包含两行：

第一行整数 $n（1 ≤ n ≤ 2×10^5）$——样本数。

第二行 $n$ 个正整数 $a_1, a_2, …, a_n（1 ≤ a_i ≤ 10^9）$。

所有测试用例的 $n$ 之和不超过 $2×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)$。

第三组和第四组测试数据中，所有样本的测量值奇偶性相同，因此无法进行任何交换。