Bubble Sort

Given an array A consisting of n natural numbers, your task is to sort it using the bubble sort algorithm and display the array after each iteration of the sorting process.

Input

The first line contains a single integer n (1 ≤ n ≤ 100), representing the size of the array. The second line contains n natural numbers, which are the elements of array A (1 ≤ A[i] ≤ 10^9).

Output

Provide n – 1 lines of output, each containing n numbers, representing the state of the array after each iteration of the sorting process.

Examples