Minimizing Haybales

문제

Bessie is bored and yet again causing trouble in Farmer John's barn. FJ has $NN$ ($1\le N\le {10}^{5}1\backslash leq\; N\; \backslash leq\; 10^5$) stacks of haybales. For each $i\in [1,N]i\backslash in\; [1,N]$, the $ii$th stack has $h_{i}h\_i$ ($1\le h_i\le {10}^{9}1\backslash le\; h\_i\backslash 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 $KK$ ($1\le K\le {10}^{9}1\backslash le\; K\backslash 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?

입력

The first line of input contains $NN$ and $KK$. The $i+1i+1$-st line contains the height of the $ii$-th haybale.

출력

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

힌트

One way that Bessie can swap the stacks is as follows:

   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

5 3
7
7
3
6
2

6
7
7
2
3