Bubble Sort

Time limit1sMemory limit64 MB

Summary

Compute the array after K left-to-right bubble sort passes over N numbers without simulating every swap.

Level: Medium6 of 10
Topics: Segment tree, Sorting, Simulation
Solved: No attempts yet

Problem

Bubble sort orders a sequence of length $N$ by comparing two adjacent values and swapping them. Call one execution of the procedure below a round.

Compare the value at position 1 with the value at position 2, and swap them if the earlier one is larger.
Compare the value at position 2 with the value at position 3, and swap them if the earlier one is larger.
Continue the same way to the right end.
Compare the value at position $N-1$ with the value at position $N$ , and swap them if the earlier one is larger.

Repeating a round $N$ times sorts the sequence in ascending order. Sechan already knows the sorted result, so he wants to look at an intermediate state instead. $N$ is very large, so imitating $K$ rounds directly takes too long. Help Sechan and write a program that computes the state of the sequence after $K$ rounds.

Input

The first line contains $N$ and $K$ , separated by a space.

The second line contains the $N$ integers of the initial sequence in order, separated by spaces.

$1 \le N \le 100000$
$1 \le K \le N$
Each term of the sequence is an integer between $1$ and $1000000000$ .

Output

Print the state of the sequence after $K$ rounds on one line. Separate the numbers with a single space.

Examples3

Example 1
Input
```
4 1
62 23 32 15
```
Expected output
```
23 32 15 62
```
Example 2
Input
```
1 1
7
```
Expected output
```
7
```
Example 3
Input
```
5 5
5 4 3 2 1
```
Expected output
```
1 2 3 4 5
```