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

Input

• Dòng đầu chứa hai số nguyên ~n~, ~k~;
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1~, ~a_2~, … , ~a_n~ (~a_i~ ≤ ~10^9~).

Output

• Gồm một dòng, chứa ~n~ 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: ~n~ ≤ 1000; ~k~ = 1;

Subtask 2: ~n~ ≤ 1000; ~k~ ≤ ~10^6~;

Subtask 3: ~n~ ≤ ~10^5~; ~k~ ≤ ~10^9~;