Thứ tự từ điển trên dãy số được định nghĩa như sau: Dãy ~A = (a_1, a_2, ..., a_n)~ được gọi là có thứ tự từ điển nhỏ hơn dãy ~B = (b_1, b_2, ..., b_n)~ nếu tồn tại một chỉ số ~i~ (~1 \le i \le n~) sao cho: ~a_1 = b_1, a_2 = b_2, ..., a_{i-1} = b_{i-1}~ và ~a_i < b_i~.

Ví dụ: ~A = (1, 4, 5, 3), B = (1, 5, 4, 3)~ thì ~A < B~ vì ~a_1 = b_1, a_2 < b_2~.

Cho một dãy số nguyên dương ~X~ gồm ~n~ phần tử ~(X_1, X_2, ..., X_n)~. Với ~i = 1, 2, ..., n-1~, gọi ~swap(i)~ là thao tác đổi chỗ hai phần tử ~X_i~ và ~X_{i+1}~ cho nhau.

Ví dụ: ~X = (1, 4, 5, 3)~, sau khi thực hiện thao tác ~swap(1)~ thì dãy ~X~ trở thành ~(4, 1, 5, 3)~. Tiếp theo sử dụng thao tác ~swap(3)~ thì dãy trở thành ~(4, 1, 3, 5)~.

Yêu cầu: Cho dãy ~X~ và số nguyên dương ~k~, xác định dãy số có thứ tự từ điển nhỏ nhất sau khi thực hiện tối đa ~k~ thao tác đổi chỗ trên dãy ~X~.

Input

• Dòng ~1~ chứa hai số nguyên dương ~n, k~ (~1 \le n \le 10^5; k \le 2 \times 10^9~).
• Dòng ~2~ chứa ~n~ số nguyên ~X_1, X_2, ..., X_n~ (~1 \le X_i \le 10^6, \forall i = 1, 2, ..., n~).

Các số trên cùng một dòng cách nhau một khoảng trắng.

Output

• Dãy ~X_1, X_2, ..., X_n~ có thứ tự từ điển nhỏ nhất sau khi thực hiện tối đa ~k~ thao tác đổi chỗ.

Sample Input 1

4 2
4 3 2 1

Sample Output 1

2 4 3 1

Sample Input 2

4 4
4 3 2 1

Sample Output 2

1 3 4 2

Subtasks