A871 | Minimizing Haybales--Platinum

Bessie is bored and yet again causing trouble in Farmer John's barn. FJ has
$N$ ($1\leq N \leq 10^5$) stacks of haybales. For each $i\in [1,N]$, the $i$th
stack has $h_i$ ($1\le h_i\le 10^9$) haybales. Bessie does not want any
haybales to fall, so the only operation she can perform is as follows:
* If two adjacent stacks' heights differ by at most $K$ ($1\le K\le 10^9$), she can swap the two stacks.
What is the lexicographically minimum sequence of heights that Bessie can
obtain after some sequence of these operations?
****Note: the time and memory limits for this problem are 4s and 512MB, twice
the defaults.****

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

Please print out $N$ lines, the $i$-th containing the height of the $i$-th
haybale in the solution.