SWAP - Hoán đổi

Trên dãy số nguyên dương \(a_1,a_2,...,a_n\), xét thao tác đổi chỗ 2 phần tử kề nhau. Cho số nguyên không âm \(k\), hãy sử dụng không quá \(k\) thao tác đổi chỗ để đưa dãy \(a_1,a_2,..,a_n\) về dãy có thứ tự từ điển lớn nhất.

Input

• Dòng đầu chứa hai số nguyên \(n, k\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1,a_2, ...,a_n(a_i ≤ 10^9)\).

Output

• Gồm 1 dòng, chứa \(n\) số nguyên là dãy nhận được sau khi đổi chỗ.

Giới hạn

• Subtask 1 (30%): \(n ≤ 1000, k ≤ 10^6\).
• Subtask 2 (20%): \(n ≤ 1000, k ≤ 10^9.\)
• Subtask 3 (50%): $n ≤ 10^5, k ≤ 10^9. $

Ví dụ

INPUT

3 2
1 2 3

OUTPUT

3 1 2