Algorithm Class - Bubble Sort 2

Interview

Time limit1sMemory limit512 MB

Summary

Simulate bubble sort on N distinct integers and print the array right after the K-th swap, or -1 if fewer than K swaps happen.

Level: Medium4 of 10
Topics: Simulation, Sorting, Implementation, Array
Solved: No attempts yet

Problem

Seojun is again working as a teaching assistant for the bubble sort class. Let us check through a problem whether the students understood what his father taught.

There is an array A containing N distinct positive integers. When A is sorted in ascending order with bubble sort, print the array A immediately after the K-th swap occurs.

The bubble sort pseudocode for an array of size N is as follows.

bubble_sort(A[1..N]) { # sorts A[1..N] in ascending order
    for last <- N downto 2
        for i <- 1 to last - 1
            if (A[i] > A[i + 1]) then A[i] <-> A[i + 1]  # swap elements
}

Input

The first line gives the size of the array A, N(5 ≤ N ≤ 10,000), and the number of swaps K(1 ≤ K ≤ N2).

The next line gives the distinct elements of the array A, A1, A2, ..., AN. (1 ≤ Ai ≤ 109)

Output

Print the array A immediately after the K-th swap on one line. If fewer than K swaps occur, print -1.

Examples2

Example 1
Input
```
6 10
4 6 5 1 3 2
```
Expected output
```
1 3 2 4 5 6
```
Example 2
Input
```
6 12
4 6 5 1 3 2
```
Expected output
```
-1
```