题目描述

n个无序整数，请用选择排序法，把它们从小到大排序并输出每一步变化过程。

输入格式

输入两行。

第一行一个整数n，表示数的个数。

第二行n个整数，每两个整数之间用空格分隔。

输出格式

输出多行，排序的过程。

每行n个整数，每两个整数之间用空格分隔。前后无多余空格。

样例

input

8
6 5 3 5 1 6 5 6

output

5 6 3 5 1 6 5 6
3 6 5 5 1 6 5 6
1 6 5 5 3 6 5 6
1 5 6 5 3 6 5 6
1 3 6 5 5 6 5 6
1 3 5 6 5 6 5 6
1 3 5 5 6 6 5 6
1 3 5 5 5 6 6 6