Description

Bessie is bored and yet again causing trouble in Farmer John's barn. FJ has $N$ stacks of haybales. For each $i\in [1,N]$, the $i$th stackhas $h_i$ haybales. Bessie does not want any haybales tofall, so the only operation she can perform is as follows:

• If two adjacent stacks' heights differ by at most $K$,she can swap the two stacks.

What is the lexicographically minimum sequence of heights that Bessie can obtainafter some sequence of these operations?

• $1\leq N \leq 10^5$
• $1\le h_i\le 10^9$
• $1\le K\le 10^9$

Input Format

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

Output Format

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

5 3
7
7
3
6
2

5 3
7
7
3
6
2

Scoring

• In 10% of all input cases, $N\le 100$
• In another 20% of all input cases, $N\le 5000$
• In the remaining 70% of input cases, there are no additionalconstraints

Note: the time and memory limits for this problem are 4s and 512MB, twicethe defaults.

Problem Credit

Problem credits: Daniel Zhang and Benjamin Qi