Challenge: Insertion Sort Steps

Lab Python Beginner 10 points

Read a list and sort it with insertion sort. After inserting each item (from the second item on), print the whole list.

Input

One line of whole numbers (at least 2).

Output

n − 1 lines.

Example

Input

7 3 5 1

Output

3 7 5 1
3 5 7 1
1 3 5 7

Sample input available Sample output available

Editor

Python

Hints

Take a[i] as the card.

Shift bigger items one place right, then drop the card into the gap.

Solution explanation

After step i, the first i + 1 items are always sorted – just like cards in your hand.

Show solution

a = list(map(int, input().split()))
for i in range(1, len(a)):
    card = a[i]
    j = i - 1
    while j >= 0 and a[j] > card:
        a[j + 1] = a[j]
        j -= 1
    a[j + 1] = card
    print(" ".join(map(str, a)))

Output

Answer