Problem 1. Minimizing Haybales

USACO 2022 January Contest, Platinum

Bessie 感到无聊，于是又在 Farmer John 的牛棚里制造麻烦。FJ 有 $N$ ($1\leq N \leq 10^5$) 堆草堆。对于每个 $i\in [1,N]$，第 $i$ 堆草堆有 $h_i$（$1\le h_i\le 10^9$）的草。Bessie 不想让任何的草倒下来，所以她唯一可以执行的操作为：

• 如果两个相邻的草堆的高度相差不超过 $K$（$1\le K\le 10^9$），她可以交换这两堆草堆。

Bessie 在一系列这样的操作之后可以得到的的字典序最小的高度序列是什么？

注意：本题的时间和内存限制分别为 4 秒和 512MB，通常限制的两倍。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$ 和 $K$。第 $i+1$ 行包含第 $i$ 堆草堆的高度。

输出格式（输出至终端 / 标准输出）：

输出 $N$ 行，第 $i$ 行包含答案中第 $i$ 堆草堆的高度。

输入样例：

5 3
7
7
3
6
2

输出样例：

6
7
7
2
3

一种 Bessie 可以交换草堆的方式如下：

   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

测试点性质： 所有测试点的 10% 满足 $N\le 100$。所有测试点的另外 20% 满足 $N\le 5000$。其余 70% 的测试点没有额外限制。

供题：Daniel Zhang，Benjamin Qi