Goran 有五个排成一排的木块。每个木块上都刻有一个 $1$ 到 $5$ 之间的数字，且每个数字在五个木块中恰好出现一次。

Goran 想要将这些木块排序，使其形成序列 $1, 2, 3, 4, 5$。他按照以下步骤进行：

1. 如果第一个木块上的数字大于第二个木块上的数字，交换它们。
2. 如果第二个木块上的数字大于第三个木块上的数字，交换它们。
3. 如果第三个木块上的数字大于第四个木块上的数字，交换它们。
4. 如果第四个木块上的数字大于第五个木块上的数字，交换它们。
5. 如果木块没有形成序列 $1, 2, 3, 4, 5$，则返回步骤 1。

编写一个程序，在给定木块初始顺序的情况下，输出每次交换后木块的顺序。

输入格式

第一行包含五个由单个空格分隔的整数，表示木块的初始顺序。

这些数字在 $1$ 到 $5$ 之间（含 $1$ 和 $5$），且没有重复。

初始顺序不会是 $1, 2, 3, 4, 5$。

输出格式

在每次发生交换后，输出当前木块的顺序，占一行，数字之间用单个空格分隔。

样例

输入样例 1

2 1 5 3 4

输出样例 1

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

输入样例 2

2 3 4 5 1

输出样例 2

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