Descripción

Fido es un perrito muy bien portado, por lo que en Navidad Santa le trajo \(N\) huesos, donde el \(i\)-ésimo hueso tiene un tamaño \(a_i\).

Desde el día en que abrió sus regalos, Fido ha jugado mucho con ellos y ahora los huesos están completamente desordenados. Asi que para Reyes, pidió una varita mágica que lo ayudara a ordenarlos.

Sin embargo, la varita resulta estar defectuosa. En lugar de ordenar los huesos de forma tradicional, solo permite realizar el siguiente tipo de operación:

• La varita mágica puede intercambiar dos huesos únicamente si sus tamaños tienen diferente paridad. Es decir, se pueden intercambiar los huesos en las posiciones \(i\) y \(j\) solo si \(a_i \bmod 2 \neq a_j \bmod 2\).

Fido quiere saber cuál es el arreglo lexicográficamente más pequeño que puede obtener aplicando esta operación cualquier cantidad de veces.

Entrada

La entrada contiene múltiples casos de prueba. La primera línea contiene un entero \(T (1\leq T \leq 10^4)\), el número de casos de prueba.

Para cada caso de prueba:

• La primera línea contiene un entero \(N (1 \leq N \leq 2\times 10^5)\), la cantidad de huesos que recibió Fido.
• La segunda línea contiene \(N\) enteros \(a_1,a_2,\ldots,a_N\) \((1 \le a_i \le 10^9)\), que representan los tamaños de los huesos.

Se garantiza que la suma de \(N\) sobre todos los casos de prueba no excede \(2 \times 10^5\).

Salida

Para cada caso de prueba, imprime \(N\) enteros correspondientes al arreglo lexicográficamente más pequeño que se puede obtener utilizando únicamente la operación permitida por la varita mágica.

Ejemplo

Entrada

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

Salida

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