Sau những ngày nuôi quân miệt mài, thầy Tina cũng đã có được một dàn chiến binh IUH hùng hậu. Mỗi người có một chỉ số chiến đấu biểu diễn bởi một số nguyên dương không vượt quá ~10^9.~ Các chiến binh này chỉ chờ ngày để chiến đấu tại đấu trường quốc gia vào tháng 11 sắp tới. Hiện tại, các chiến binh đang đứng thành một hàng dọc để được thầy Tina kiểm tra sức khỏe. Tuy nhiên, để biểu thị sức mạnh trước các trường khác thì thầy Tina muốn cho cho bạn có chỉ số sức mạnh càng cao thì càng phải được đứng trước. Bằng cách dùng không quá ~k~ lần swap hai bạn liền kề, hỏi thầy có thể tạo thành một dãy chỉ số chiến đấu mới với thứ tự từ điển lớn nhất là bao nhiêu?

Input

Dòng đầu tiên gồm số nguyên dương ~n, k~ trong đó ~1 \le n \le 10^5~ và ~0 \le k \le 10^9.~

Dòng tiếp theo gồm ~n~ số nguyên cho biết chỉ số chiến đấu của các chiến binh, các số này không quá ~10^9~ và không nhất thiết phân biệt.

Output

In ra danh sách chỉ số chiến đấu mới sau khi đã sắp xếp.

Sample input 1

3 2
1 2 3

Sample output 1

3 1 2

Sample input 2

4 2
3 2 2 1

Sample output 2

3 2 2 1

Giải thích: trong VD1, ta sẽ đổi ~(1,2,3) \to (1,3,2) \to (3,1,2)~, còn với VD2, do bộ ~(3,3,2,1)~ có thứ tự từ điển lớn nhất rồi nên không cần phải đổi gì nữa.