Elverişsiz Yer Değiştirmeler#13110

Elverişsiz Yer Değiştirmeler

1 saniye
256 megabayt

Size tam sayılardan oluşan bir a_1, a_2, \ldots, a_n dizisi veriliyor.

Bir işlemde, a_i - a_j farkı ile bölünebilen iki farklı ve indisi seçip a_i ve a_j değerlerinin yerlerini değiştirebilirsiniz. İndislerin komşu olması gerekmez. İstediğiniz kadar, muhtemelen hiç, işlem yapabilirsiniz.

Elde edilebilecek sözlüksel olarak en küçük diziyi bulun.

Bir b_1, \ldots, b_n dizisi, farklı oldukları ilk konumunda b_i < c_i oluyorsa c_1, \ldots, c_n dizisinden sözlüksel olarak küçüktür. Elemanlar tam sayı olarak karşılaştırılır, yani örneğin -5 < 2.

Giriş

İlk satırda bir tam sayı (1 \le t \le 10^4) — test durumlarının sayısı verilir.

Her test durumu iki satırdan oluşur. İlk satırda dizinin uzunluğu olan bir tam sayı (1 \le n \le 3 \cdot 10^5) verilir. İkinci satırda tam sayı a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9) verilir.

Tüm test durumları boyunca değerlerinin toplamı 3 \cdot 10^5 değerini aşmaz.

Çıktı

Her test durumu için tam sayı içeren bir satır yazdırın: elde edilebilecek sözlüksel olarak en küçük dizi.

Örnekler

Örnek 1

Loading
Loading

Not

Birinci test durumunda önce a_1 ile a_4, sonra a_2 ile a_3, sonra a_3 ile a_6, ardından a_4 ile a_5 yer değiştirilebilir. Dizi 2, -6, 0, 5, 8, 3 olur. Daha küçük bir dizi elde edilemeyeceği gösterilebilir.

İkinci test durumunda a_1 ile a_5, sonra da a_2 ile a_4 yer değiştirilebilir; bu da 4, -4, 7, -1, 10 dizisini verir.

Üçüncü test durumunda iki elemanın hiçbir farkı ile bölünemediğinden hiçbir işlem mümkün değildir ve dizi değişmez.