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 在执行一系列此类操作后，能得到的字典序最小的高度序列是什么？

输入格式

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

输出格式

请输出 $N$ 行，第 $i$ 行包含最优解中第 $i$ 堆干草捆的高度。

样例

输入格式 1

5 3
7
7
3
6
2

输出格式 1

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% 的测试数据中，没有额外限制