Əlverişsiz yerdəyişmələr#13110

Əlverişsiz yerdəyişmələr

1 saniyə
256 meqabayt

Sizə tam ədədlərdən ibarət a_1, a_2, \ldots, a_n massivi verilib.

Bir əməliyyatda a_i - a_j fərqi -ə bölünən iki müxtəlif və indeksini seçib a_i və a_j qiymətlərinin yerini dəyişə bilərsiniz. İndekslərin qonşu olması vacib deyil. İstənilən sayda, o cümlədən sıfır sayda əməliyyat yerinə yetirə bilərsiniz.

Alına bilən leksikoqrafik baxımdan ən kiçik massivi tapın.

b_1, \ldots, b_n massivi c_1, \ldots, c_n massivindən leksikoqrafik baxımdan kiçikdir, əgər onların fərqləndiyi ilk mövqeyində b_i < c_i olarsa. Elementlər tam ədədlər kimi müqayisə olunur, məsələn, -5 < 2.

Giriş

Birinci sətirdə bir tam ədəd (1 \le t \le 10^4) — test hallarının sayı verilir.

Hər test halı iki sətirdən ibarətdir. Birinci sətirdə massivin uzunluğu olan (1 \le n \le 3 \cdot 10^5) tam ədədi verilir. İkinci sətirdə tam ədəd a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9) verilir.

Bütün test halları üzrə qiymətlərinin cəmi 3 \cdot 10^5-i aşmır.

Çıxış

Hər test halı üçün bir sətirdə tam ədəd çap edin: alına bilən leksikoqrafik baxımdan ən kiçik massiv.

Nümunələr

Nümunə 1

Loading
Loading

Qeyd

Birinci test halında a_1 və a_4, sonra a_2 və a_3, sonra a_3 və a_6, daha sonra isə a_4 və a_5 yerlərini dəyişmək olar. Massiv 2, -6, 0, 5, 8, 3 olur. Daha kiçik massiv almağın mümkün olmadığını göstərmək olar.

İkinci test halında a_1 və a_5, sonra isə a_2 və a_4 yerlərini dəyişmək olar, nəticədə 4, -4, 7, -1, 10 alınır.

Üçüncü test halında iki elementin heç bir fərqi -ə bölünmür, ona görə də heç bir əməliyyat mümkün deyil və massiv dəyişmir.