To celebrate the upcoming CCC (Canadian Computing Contest), Max decided to define a new sorting algorithm called Bob Sort.
Bob Sort involves rounds of sorting.
For the round, Bob Sort looks at the rightmost digits, :
If there are fewer than digits in element , the left-aligned missing digits are set to .
Then, Bob Sort sorts the elements by their corresponding value in non-decreasing order.
Can you Bob Sort the array into increasing order?
All are distinct.
The first line will contain , the number of elements in the array.
The next line will contain space-separated integers, the elements of the array.
Output lines, the array after each round of sorting.
Note: Within a round, ties do not need to be broken between elements with the same value, .
Sample Input 1
6 2 105 12 1 15 65
Sample Output 1
1 2 12 105 15 65 1 2 105 12 15 65 1 2 12 15 65 105
Sample Input 2
Sample Output 2
100 100 100