P8099 [USACO22JAN] Minimizing Haybales P

Bessie is bored again, so she is causing trouble in Farmer John's barn. FJ has $N$ ($1 \le N \le 10^5$) haybale stacks. For each $i \in [1,N]$, the $i$-th stack has height $h_i$ ($1 \le h_i \le 10^9$). Bessie does not want any hay to fall over, so the only operation she can do is: - If the height difference between two adjacent stacks is at most $K$ ($1 \le K \le 10^9$), she can swap these two stacks. After a sequence of such operations, what is the lexicographically smallest height sequence Bessie can obtain?

The first line contains $N$ and $K$. Line $i+1$ contains the height of the $i$-th haybale stack.

Output $N$ lines. Line $i$ contains the height of the $i$-th haybale stack in the answer.

Sample Explanation. One possible way for Bessie to swap the haybales is: ```plain 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 ``` Constraints. - For $10\%$ of all testdata, $N \le 100$. - For another $20\%$ of all testdata, $N \le 5000$. - For the remaining $70\%$ of the testdata, there are no additional constraints. Problem by: Daniel Zhang, Benjamin Qi. Translated by ChatGPT 5