Костя вивчає алгоритм сортування «бульбашкою», і для того щоб зрозуміти що відбувається з масивом вирішив виводити масив після кожної ітерації сортування. Допоможіть Кості розібратися з алгоритмом сортування «бульбашка» Задано масив ~А~ із ~n~ натуральних чисел, впорядкуйте його за допомогою сортування бульбашкою, і виведіть масив після кожної ітерації сортування.

Формат вхідних даних

У першому рядку вхідного файлу знаходиться єдине ціле число ~n~~(1 ≤ n ≤ 100)~ – розмір масиву.

В наступному рядку знаходяться n натуральних чисел, розділених пробілом – елементи масиву ~A~~(1 ≤ A_i ≤ 10^9)~.

Формат вихідних даних

Виведіть ~n – 1~ рядків, у кожному з яких виведіть ~n~ чисел – масив після чергової ітерації сортування.

Приклад вхідних даних

6
5 4 4 2 3 1

Приклад вихідних даних

4 4 2 3 1 5
4 2 3 1 4 5
2 3 1 4 4 5
2 1 3 4 4 5
1 2 3 4 4 5