3331003 - 冒泡自动机

通过次数

15

提交次数

57

Time Limit : 1 秒
Memory Limit : 128 MB

海码这段时间在学习冒泡排序算法。海码觉得冒泡排序的过程太复杂,搞不清楚。

为了帮助海码理解冒泡排序,请你设计一个可以输出冒泡排序过程的小程序。

届时,海码会重重感谢你,给你一个100分。

Input

第一行,一个不超过30的正整数n

第二行,依次输入n个整数,用空格隔开

第三行,输入整数轮次round,题目保证round的值不超过n-1,且round不会是负数

第四行,输入一个字符c,'s'表示升序(从小到大),'j'表示降序(从大大小)

Output

输出前round轮的排序结果。

一行输出一轮排序后的结果,相邻两数用空格隔开。

Examples

Input

5
5 4 3 2 1
4
s

Output

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

Input

6
1 2 5 3 9 10
5
j

Output

2 5 3 9 10 1
5 3 9 10 2 1
5 9 10 3 2 1
9 10 5 3 2 1
10 9 5 3 2 1