Description

Given a sequence $a$ consisting of five numbers, each of $1 \sim 5$ appears exactly once among these five numbers. Now sort the sequence using the following operations.

1. If $a_1 > a_2$, swap $a_1$ and $a_2$.
2. If $a_2 > a_3$, swap $a_2$ and $a_3$.
3. If $a_3 > a_4$, swap $a_3$ and $a_4$.
4. If $a_4 > a_5$, swap $a_4$ and $a_5$.
5. If the sequence has not become $\{1, 2, 3, 4, 5\}$, go back to step 1 and continue sorting.

Output the current sequence after each swap.

Input Format

The input contains only one line with five numbers, representing the sequence $a$.

Output Format

Output several lines. Each line contains five integers separated by spaces, representing the sequence after one swap.

2 1 5 3 4

1 2 5 3 4
1 2 3 5 4
1 2 3 4 5

2 3 4 5 1

2 3 4 1 5
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5

Hint

Constraints

For all test points, it is guaranteed that $1 \leq a_i \leq 5$, all $a_i$ are distinct, and the sequence is not strictly increasing.

Hint

It can be proven that the number of swaps does not exceed $25$.

This problem is translated from COCI2008-2009 CONTEST #4 T1 MJEHURIC.

Translated by ChatGPT 5