题目描述

小明正在观察排序算法的执行过程。

给定一个数组，以及排序算法类型 type 和轮数 k，请你模拟该排序算法执行前 k 轮后的数组状态。

排序算法类型如下：

1. type = 1：选择排序。第 i 轮从第 i 个位置到末尾找最小值，并与第 i 个位置交换；
2. type = 2：冒泡排序。第 i 轮从左到右比较相邻元素，把当前未排序部分的最大值冒泡到右侧；
3. type = 3：插入排序。第 i 轮将第 i + 1 个元素插入到前面已经有序的部分中。

数组下标从 1 开始描述。所有排序都按照从小到大进行。

输入格式

输入共 2 行。

第 1 行输入三个整数 type、n 和 k，表示排序算法类型、数组长度和模拟轮数。

第 2 行输入 n 个整数，表示初始数组。

输出格式

输出一行，包含执行前 k 轮后的数组。

样例

2 5 2
5 1 4 2 3

1 2 3 4 5

样例说明

样例使用冒泡排序。

第 1 轮后，数组变为 1 4 2 3 5。

第 2 轮后，数组变为 1 2 3 4 5。

数据范围

• 对于 100% 的数据，满足 1 <= type <= 3
• 1 <= n <= 100
• 0 <= k <= n
• -10000 <= 数组元素 <= 10000