当前没有测试数据。

C. Isamatdin and His Magic Wand!

题目描述

Isamatdin 有 $n$ 个玩具排成一行，第 $i$ 个玩具上有一个整数 $a_i$。他想把这些玩具排序，否则他的妈妈会责备他。

但是 Isamatdin 不喜欢整理玩具，于是他的朋友 JahonaliX 给了他一根魔法棒来帮忙。不幸的是，这根魔法棒有点问题。

这根魔法棒只能在两个玩具的数值奇偶性不同时交换它们。也就是说，只有当 $a_i \bmod 2 \ne a_j \bmod 2$ 时，才能交换位置 $(i, j)$ 的两个玩具。

现在，他想知道：在这种限制下，能够得到的字典序最小的序列是什么。

字典序定义：序列 $p$ 比序列 $q$ 小，当且仅当存在一个位置 $i$，使得对于所有 $j < i$ 有 $p_j = q_j$，且 $p_i < q_i$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

保证所有测试用例的 $n$ 之和不超过 $2 \times 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

提示

只能交换奇偶性不同的数。可以将所有奇数和偶数分别取出排序，然后按原位置的奇偶性依次放回，以得到字典序最小结果。