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

Ràng buộc & Subtasks