Cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là tính nội dung của mảng sau \(k\) vòng sắp xếp nổi bọt.

Trong một vòng, ta duyệt mảng từ trái sang phải và hoán đổi hai phần tử kề nhau nếu chúng đang sai thứ tự.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\): kích thước mảng và số vòng.
• Dòng tiếp theo chứa \(n\) số nguyên \(x_1,x_2,\dots,x_n\): các phần tử của mảng.

Output

• In ra \(n\) số nguyên: nội dung của mảng sau \(k\) vòng.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(0 \le k \le 10^9\)
• \(1 \le x_i \le 10^9\)

Example

5 2
3 2 4 1 4

2 1 3 4 4