Lexicographically Smallest Permutation with Exactly K Adjacent Swaps

You are given a permutation \(p\) of numbers \(1\) to \(n\) (1-indexed). You are allowed to perform exactly \(K\) adjacent swaps. In each operation, you can choose any index \(i\) such that \(1 \le i < n\) and swap \(p_i\) and \(p_{i+1}\). Among all the outcomes obtainable after exactly \(K\) swaps, output the lexicographically smallest permutation.

Note: An adjacent swap always changes the permutation. When the lexicographically smallest permutation achievable by at most \(K\) swaps can be obtained using fewer than \(K\) swaps, you are forced to perform extra swaps. Since adjacent swaps are involutions in pairs, if the remaining number of swaps is even, you can waste them by swapping a pair and then swapping back. However, if the remaining moves are odd you must perform one additional swap which might worsen the lexicographical order. Thus, the answer is derived as follows:

1. Use a greedy algorithm to achieve the lexicographically smallest permutation using at most swaps. For each position \(i\) from \(1\) to \(n\), find the minimum element in the subarray from \(i\) to \(\min(n, i+K)\) (since moving an element from position \(j\) to \(i\) costs \(j-i\) swaps) and bring it to position \(i\) by swapping adjacent elements. Deduct the corresponding cost from \(K\). Let the resulting array be \(Q\) and let \(S\) be the total number of swaps used.

2. Let \(R = K - S\) be the remaining swaps. If \(R\) is even, then \(Q\) is the answer. Otherwise (if \(R\) is odd), among all permutations obtainable by performing exactly one additional adjacent swap on \(Q\), choose the one that is lexicographically smallest.

It is guaranteed that a solution always exists.

inputFormat

The first line contains two integers \(n\) and \(K\) separated by a space.

The second line contains \(n\) distinct integers \(p_1, p_2, ..., p_n\) representing the permutation.

outputFormat

Output the lexicographically smallest permutation obtainable after exactly \(K\) adjacent swaps. Print the permutation as \(n\) space-separated integers.

sample

3 1
3 1 2

1 3 2