Description

Given a permutation $p$ of $1\sim n$, with indices starting from $1$.

You must perform exactly $K$ operations. In each operation, you may choose any $1\le i<n$ and swap $p_i$ and $p_{i+1}$. After all swaps are done, what is the lexicographically smallest permutation $p$?

Input Format

The first line contains two non-negative integers $n,K$, representing the number of elements in the permutation and the number of swaps.

The next line contains $n$ integers describing the permutation $p$.

Output Format

Output one line with $n$ positive integers separated by spaces, describing the permutation after all swaps are completed.

5 2
2 1 4 3 5

1 2 3 4 5

5 3
5 4 3 2 1

2 5 4 3 1

5 6
5 4 3 2 1

1 3 5 4 2

Hint

This problem uses bundled testdata.

For all testdata, $1\le n\le 5\times 10^5$, $0\le K\le 10^{12}$.

The detailed Constraints are shown in the table below:

Translated by ChatGPT 5