Bessie đang buồn chán và lại một lần nữa gây rắc rối trong chuồng của Nông dân John. FJ có \(N\) (\(1\le N\le 10^5\)) chồng kiện cỏ khô. Với mỗi \(i\in[1,N]\), chồng thứ \(i\) có \(h_i\) (\(1\le h_i\le 10^9\)) kiện cỏ. Bessie không muốn kiện cỏ nào bị rơi, nên thao tác duy nhất cô có thể thực hiện là:

• Nếu chiều cao của hai chồng kề nhau chênh lệch không quá \(K\) (\(1\le K\le 10^9\)), cô có thể đổi chỗ hai chồng.

Dãy chiều cao nhỏ nhất theo thứ tự từ điển mà Bessie có thể thu được sau một chuỗi các thao tác này là gì?

Lưu ý: giới hạn thời gian và bộ nhớ cho bài này lần lượt là 4 giây và 512 MB, gấp đôi giá trị mặc định.

Dữ liệu vào

Dòng đầu chứa \(N\) và \(K\). Dòng thứ \(i+1\) chứa chiều cao của chồng kiện cỏ thứ \(i\).

Dữ liệu ra

In \(N\) dòng, dòng thứ \(i\) chứa chiều cao của chồng kiện cỏ thứ \(i\) trong lời giải.

Phân nhóm

• Trong 10% số dữ liệu vào, \(N\le 100\).
• Trong 20% số dữ liệu vào khác, \(N\le 5000\).
• Trong 70% số dữ liệu vào còn lại, không có ràng buộc bổ sung.

Ví dụ

5 3
7
7
3
6
2

6
7
7
2
3

   7 7 3 6 2
-> 7 7 6 3 2
-> 7 7 6 2 3
-> 7 6 7 2 3
-> 6 7 7 2 3

Nguồn

USACO 2022 January Contest, Platinum — Minimizing Haybales: https://usaco.org/index.php?page=viewproblem2&cpid=1188

Tác giả: Daniel Zhang và Benjamin Qi.