Problem Description

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?

Input Format

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

Output Format

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

5 3
7
7
3
6
2

6
7
7
2
3

Hint

Sample Explanation.

One possible way for Bessie to swap the haybales is:

   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