## USACO 2022 January Contest, Platinum

## Problem 1. Minimizing Haybales

Contest has ended.

**Log in to allow submissions in analysis mode**

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:

Contest has ended. No further submissions allowed.
- 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.****

#### INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains $N$ and $K$. The $i+1$-st line contains the height of the $i$-th haybale.#### OUTPUT FORMAT (print output to the terminal / stdout):

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

5 3 7 7 3 6 2

#### SAMPLE OUTPUT:

6 7 7 2 3

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

#### 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 additional constraints

Problem credits: Daniel Zhang and Benjamin Qi