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ỏ đứng liền kề nhau bao nhiêu lần tuỳ ý, với điều kiện chênh lệch chiều cao của hai đống đó không vượt quá $K$.

Hãy tìm dãy chiều cao 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, dòng thứ $i$ là chiều cao của đống cỏ thứ $i$ trong dãy tìm được.

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ụ