Sorting Wooden Pieces

Time limit1sMemory limit128 MB

Summary
Simulate repeated bubble-sort passes on five labeled pieces, printing the arrangement after every swap until sorted.
Level

Easy2 of 10

Topics
Simulation, Sorting, Array
Solved
No attempts yet

Problem

Donghyuk has five wooden pieces, each labeled with one of the numbers from 1 to 5. Every number appears on exactly one piece. He wants to arrange the pieces in the order 1 2 3 4 5 by repeatedly performing the following process.

  1. If the first piece has a larger number than the second piece, swap the two pieces.
  2. If the second piece has a larger number than the third piece, swap the two pieces.
  3. If the third piece has a larger number than the fourth piece, swap the two pieces.
  4. If the fourth piece has a larger number than the fifth piece, swap the two pieces.
  5. If the pieces are still not in the order 1 2 3 4 5, go back to step 1.

Given the initial order of the pieces, print the order of the pieces every time a swap is made.

Input

The first line contains the five numbers on the pieces in their current order.

Each number is between 1 and 5 inclusive, no number appears more than once, and the initial order is not 1 2 3 4 5.

Output

Whenever two pieces are swapped, print one line containing the order of the pieces after that swap.

Examples2

  1. Example 1

    Input
    2 1 5 3 4
    Expected output
    1 2 5 3 4
1 2 3 5 4
1 2 3 4 5

  2. Example 2

    Input
    2 3 4 5 1
    Expected output
    2 3 4 1 5
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5