Trên dãy số nguyên dương ~𝑎_1,a_2,…,𝑎_𝑛~, 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 ~𝑎_1,a_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,a_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ỗ.

Ví dụ:

Input

3 2
1 2 3

Output

3 1 2

• Subtask 1: ~𝑛 ≤ 1000; k= 1;~
• Subtask 2: ~𝑛 ≤ 1000; ≤ 10^6;~
• Subtask 3: ~𝑛 ≤ 10^5; k ≤ 10^9;~