打印每一趟冒泡排序

为了便于较好的观察每趟走访的数据结果，请将每一趟数据打印出来~

Input

第一行一个整数N(N<=2000)，表示有N个整数需要排序。 接下来一行有N个整数ai(1<=ai<=1e9)，表示待排序数列。 

Output

输出N-1行每一趟排序结果 

Examples

Input

5
5 4 3 2 1

Output

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

来源

lema
Time limit 1 second
Memory limit 128 MB
讨论 统计