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.
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.
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ə 1
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.