Library method

Demonstrate how the insertion sort algorithm works to sort an array in ascending order. For this task, display the state of the array after each insertion step on a new line. If the array is already sorted initially, no output is required.

Input

The first line contains the integer N (1 ≤ N ≤ 100), representing the number of elements in the array. The second line provides the array itself: a sequence of natural numbers, each not exceeding 10^9.

Output

Output the array's state after each insertion, with each line containing N numbers.

Examples