题目描述

给定一个长度为 $n$ 的整数序列 $a$。

你可以进行任意次操作：选择两个位置 $i,j$，当且仅当 $a_i$ 和 $a_j$ 奇偶性不同，即一个为奇数、一个为偶数时，可以交换这两个数。

请输出通过这些操作能够得到的字典序最小的序列。

字典序定义：若两个序列从左到右第一次不同的位置上，一个序列的数更小，则这个序列字典序更小。

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试数据包含两行：

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

保证所有测试数据的 $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)$。

第三、四组测试数据中，所有数奇偶性相同，任意两个数都不能交换，因此序列保持不变。

数据范围

• $1 \le t \le 10^4$
• $1 \le n \le 2\cdot 10^5$
• $1 \le a_i \le 10^9$
• 所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$

来源

Codeforces Round 1062 (Div. 4), Problem C - Isamatdin and His Magic Wand!