Незручні обміни#13110

Незручні обміни

1 секунда
256 мегабайтів

Задано масив цілих чисел a_1, a_2, \ldots, a_n.

За одну операцію можна вибрати два різні індекси та такі, що a_i - a_j ділиться на , і поміняти місцями значення a_i та a_j. Індекси не обов'язково сусідні. Можна виконати будь-яку кількість операцій, зокрема жодної.

Знайдіть лексикографічно найменший масив, який можна отримати.

Масив b_1, \ldots, b_n лексикографічно менший за масив c_1, \ldots, c_n, якщо b_i < c_i на першій позиції , де вони відрізняються. Елементи порівнюються як цілі числа, тож, наприклад, -5 < 2.

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 10^4) — кількість тестових випадків.

Кожен тестовий випадок складається з двох рядків. Перший рядок містить ціле число (1 \le n \le 3 \cdot 10^5) — довжину масиву. Другий рядок містить цілих чисел a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9).

Сума за всіма тестовими випадками не перевищує 3 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть один рядок з цілими числами: лексикографічно найменший масив, який можна отримати.

Приклади

Приклад 1

Loading
Loading

Примітка

У першому тестовому випадку можна поміняти місцями a_1 і a_4, потім a_2 і a_3, потім a_3 і a_6, а потім a_4 і a_5. Масив стане 2, -6, 0, 5, 8, 3. Можна показати, що меншого масиву отримати неможливо.

У другому тестовому випадку можна поміняти місцями a_1 і a_5, а потім a_2 і a_4 й отримати 4, -4, 7, -1, 10.

У третьому тестовому випадку жодна різниця двох елементів не ділиться на , тому жодна операція неможлива і масив не змінюється.