Intercambios inconvenientes#13110

Intercambios inconvenientes

1 segundo
256 megabytes

Se te da un arreglo a_1, a_2, \ldots, a_n de números enteros.

En una operación puedes elegir dos índices distintos y tales que a_i - a_j sea divisible entre e intercambiar los valores a_i y a_j. Los índices no tienen que ser adyacentes. Puedes realizar cualquier cantidad de operaciones, posiblemente ninguna.

Encuentra el arreglo lexicográficamente más pequeño que se puede obtener.

Un arreglo b_1, \ldots, b_n es lexicográficamente menor que un arreglo c_1, \ldots, c_n si b_i < c_i en la primera posición en la que difieren. Los elementos se comparan como números enteros, así que, por ejemplo, -5 < 2.

Entrada

La primera línea contiene un único entero (1 \le t \le 10^4) — la cantidad de casos de prueba.

Cada caso de prueba consta de dos líneas. La primera línea contiene un entero (1 \le n \le 3 \cdot 10^5) — la longitud del arreglo. La segunda línea contiene enteros a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9).

La suma de sobre todos los casos de prueba no supera 3 \cdot 10^5.

Salida

Para cada caso de prueba imprime una línea con enteros: el arreglo lexicográficamente más pequeño que se puede obtener.

Ejemplos

Ejemplo 1

Loading
Loading

Nota

En el primer caso de prueba se pueden intercambiar a_1 y a_4, luego a_2 y a_3, luego a_3 y a_6, y después a_4 y a_5. El arreglo pasa a ser 2, -6, 0, 5, 8, 3. Se puede demostrar que no es posible obtener un arreglo menor.

En el segundo caso de prueba se pueden intercambiar a_1 y a_5, y luego a_2 y a_4, lo que da 4, -4, 7, -1, 10.

En el tercer caso de prueba ninguna diferencia de dos elementos es divisible entre , por lo que no es posible ninguna operación y el arreglo no cambia.