Thu nhỏ đống cỏ

Có $N$ đống cỏ xếp thành một hàng, đống thứ $i$ có chiều cao $h_i$. Bạn có thể hoán đổi hai đống cỏ liền kề bất kỳ số lần, với điều kiện chênh lệch chiều cao của chúng không vượt quá $K$.

Hãy tìm dãy chiều cao theo thứ tự nhỏ nhất theo thứ tự từ điển có thể đạt được.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $K$.

• $N$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên $h_i$.

Dữ liệu ra

In ra $N$ dòng: chiều cao các đống cỏ sau khi sắp xếp theo thứ tự nhỏ nhất từ điển.

Ràng buộc

• $1\le N\le {10}^5$
• $1\le h_i\le {10}^9$
• $1\le K\le {10}^9$

Subtask 1 (10%): $N\le 100$

Subtask 2 (20%): $N\le 5000$

Subtask 3 (70%): Không có ràng buộc thêm.

Ví dụ

Ghi chú

Dãy $A$ nhỏ hơn dãy $B$ theo thứ tự từ điển nếu tồn tại chỉ số $i$ đầu tiên mà $A_i<B_i$.