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

Input

• Dòng đầu chứa hai số nguyên 𝑛, 𝑘;

• Dòng thứ hai gồm 𝑛 số nguyên dương 𝑎1, 𝑎2, … , 𝑎𝑛 (𝑎𝑖 ≤ 10^9).

Output

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

Sample Input

3 2 
1 2 3

Sample Output

3 1 2

Ràng buộc

Subtask 1: 𝑛 ≤ 1000; 𝑘 = 1; 
Subtask 2: 𝑛 ≤ 1000; 𝑘 ≤ 10^6; 
Subtask 3: 𝑛 ≤ 10^5; 𝑘 ≤ 10^9;