To celebrate the upcoming CCC (Canadian Computing Contest), Max decided to define a new sorting algorithm called Bob Sort.

Bob Sort involves ~\lfloor \log_{10}(\max(A_i)) + 1 \rfloor~ rounds of sorting.

For the ~r^\text{th}~ round, Bob Sort looks at the ~r~ rightmost digits, ~d_i~:

If there are fewer than ~r~ digits in element ~i~, the left-aligned missing digits are set to ~0~.

Then, Bob Sort sorts the elements by their corresponding value ~(d_i)~ in non-decreasing order.

Can you Bob Sort the array into increasing order?

Constraints

~1 \le N \le 100\,000~

~1 \le A_i \le 10^9~

All ~A_i~ are distinct.

Input Specification

The first line will contain ~N~, the number of elements in the array.

The next line will contain ~N~ space-separated integers, the elements of the array.

Output Specification

Output ~\lfloor \log_{10}(\max(A_i)) + 1 \rfloor~ 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, ~d_i~.

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

1
100

Sample Output 2

100
100
100