Tý có một hoán vị \(A\) gồm \(N\) số nguyên dương từ \(1\) đến \(N\). Tý muốn biến đổi hoán vị này để thu được một hoán vị mới có thứ tự từ điển nhỏ nhất có thể.

Quy tắc biến đổi: Tý được phép tráo đổi vị trí của hai phần tử kề nhau trong hoán vị \(A\) tối đa \(K\) lần. Hãy giúp Tý tìm ra hoán vị nhỏ nhất từ điển sau khi thực hiện không quá \(K\) lần đổi chỗ.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(K\) (\(1 \le N \le 10^5\), \(0 \le K \le 10^{10}\)).
• Dòng hai chứa \(N\) số nguyên là hoán vị ban đầu \(A_1, A_2, \dots, A_N\).

Định dạng đầu ra

• In ra \(N\) số nguyên trên một dòng cách nhau bởi dấu cách là hoán vị nhỏ nhất từ điển thu được.

Ví dụ

Input:

5 3
4 5 1 2 3

Output:

1 4 5 2 3