Challenge: Bubble Sort, Pass by Pass

Lab Python Beginner 10 points

Read a list of numbers and bubble sort it. After every pass print the list (numbers separated by spaces). Stop as soon as a pass makes no swaps (still print that pass).

Input

One line of whole numbers (at least 2).

Output

One line per pass.

Example

Input

5 1 4 2 8

Output

1 4 2 5 8
1 2 4 5 8
1 2 4 5 8

Sample input available Sample output available

Editor

Python

Hints

The outer loop counts passes; the inner loop compares neighbours.

Print after each pass, then break if nothing was swapped.

Solution explanation

The swapped flag lets bubble sort stop early, so a sorted list takes only one pass.

Show solution

a = list(map(int, input().split()))
n = len(a)
for done in range(n - 1):
    swapped = False
    for i in range(n - 1 - done):
        if a[i] > a[i + 1]:
            a[i], a[i + 1] = a[i + 1], a[i]
            swapped = True
    print(" ".join(map(str, a)))
    if not swapped:
        break

Output

Answer