Isamatdin and His Magic Wand!

Key observation

The wand can swap two values exactly when their parities differ. That sounds restrictive, but it is only restrictive in one case: when the whole array has the same parity.

If all values are odd, every pair is odd-odd, so no swap is legal. If all values are even, every pair is even-even, same deal. The answer is just the original array.

Now suppose the array has at least one odd and at least one even.

Then any odd-even pair can be swapped directly. The only suspicious part is whether we can swap two odds, or two evens. Turns out yes, because the opposite parity value can act as a buffer.

Say we want to swap two odd values $x$ and $y$, and somewhere else there is an even value $z$:

1. swap $x$ with $z$,
2. swap $y$ with $z$,
3. swap $x$ with $z$ again.

After these three legal swaps, $x$ and $y$ have exchanged positions, and $z$ is back where it started. Same logic works for swapping two evens using an odd buffer.

So when both parities exist, we can perform any transposition of two elements. And since arbitrary transpositions generate every permutation, we can rearrange the array however we want.

The lexicographically smallest permutation of a multiset is just the sorted array. No galaxy-brain DP, no cursed graph theory hiding under the bed. Sort it and move on.

Algorithm

For each test case:

1. Check whether the array contains an odd number.
2. Check whether the array contains an even number.
3. If both exist, sort the whole array.
4. Otherwise, leave it unchanged.
5. Print the result.

Correctness proof

We prove that the algorithm outputs the lexicographically smallest reachable array.

If the array contains only one parity, then for every pair of positions $(i,j)$, $a_i \bmod 2 = a_j \bmod 2$. Therefore no swap is legal. The only reachable array is the original array, so the algorithm is correct in this case.

Now suppose the array contains both parities. Any two elements of different parity can be swapped directly by the operation.

For two elements of the same parity, choose any element of the opposite parity as a buffer. Using the three-swap sequence described above, those two same-parity elements can be swapped while the buffer returns to its original position. Every swap in the sequence is legal because it is always between opposite parities.

Therefore, when both parities exist, any pair of elements can be swapped. Since any permutation can be built from pairwise swaps, every permutation of the array is reachable.

Among all permutations of the array, the lexicographically smallest one is the nondecreasing sorted order. The algorithm outputs exactly that order, so it is correct.

Complexity

Checking parity takes $O(n)$. Sorting takes $O(n \log n)$ if needed. Across all test cases, the total $n$ is at most $2 \cdot 10^5$, so this easily fits.