Trên dãy số nguyên dương 𝑎₁,₂,…,𝑎_𝑛, xét thao tác đổi 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 𝑎₁,₂,…,𝑎_𝑛 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 𝑎₁,₂,…,𝑎_𝑛 (𝑎_𝑖 ≤ 10⁹).

Output

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

Subtask 3: 𝑛 ≤ 10⁵; ≤ 10⁹;