题目描述

给定一个整数数组，使用选择排序算法对其进行升序排序，并输出每一趟排序结束后的数组状态。

要求：必须严格执行 比较成立就交换 a[i] 和 a[j] 的选择排序算法，其他排序方法或传统选择排序无法得到正确的中间结果。

输入格式

• 第一行包含一个整数 n（1 ≤ n ≤ 100），表示数组长度。
• 第二行包含 n 个整数，每个整数的范围是 0-100，用空格分隔，表示待排序的数组。

输出格式

输出 n-1 行，每行表示选择排序每一趟结束后的数组状态，元素之间用空格分隔。

示例

输入

5
5 3 4 7 2

输出

2 5 4 7 3
2 3 5 7 4
2 3 4 7 5
2 3 4 5 7