Given an array of \(N\) integers \(\{a_1, a_2, a_3, ..., a_N\}\), sort the array in non-descending order using the bubble sort algorithm, starting from \(a_1\) and ending at \(a_N\).

*Note: although there is no penalty for this problem, ensure that you decrement the upper bound with each loop to avoid comparing already sorted portions of the array!

Input Specification

The first line of input will contain \(N\) \((1 \le N \le 200)\).

The second line of input will contain \(N\) space-separated integers, representing each element \(a_i\) \((0 \le a \le 10^6)\) in the array.

Output Specification

On separate lines, output \(N\) space-separated integers representing the state of the array after each swap.

Sample Input 1

9
25 9 11 31 23 2 42 15 26

Sample Output 1

9 25 11 31 23 2 42 15 26
9 11 25 31 23 2 42 15 26
9 11 25 23 31 2 42 15 26
9 11 25 23 2 31 42 15 26
9 11 25 23 2 31 15 42 26
9 11 25 23 2 31 15 26 42
9 11 23 25 2 31 15 26 42
9 11 23 2 25 31 15 26 42
9 11 23 2 25 15 31 26 42
9 11 23 2 25 15 26 31 42
9 11 2 23 25 15 26 31 42
9 11 2 23 15 25 26 31 42
9 2 11 23 15 25 26 31 42
9 2 11 15 23 25 26 31 42
2 9 11 15 23 25 26 31 42

Sample Input 2

1
0

Sample Output 2

No lines of output.