Костя вивчає алгоритм сортування «бульбашкою», і для того щоб зрозуміти що відбувається з масивом вирішив виводити масив після кожної ітерації сортування. Допоможіть Кості розібратися з алгоритмом сортування «бульбашка» Задано масив \(А\) із \(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