Minimizing Haybales

Time limit4sMemory limit512 MB

Summary

Given stacks of haybales where adjacent stacks whose heights differ by at most K can swap, output the lexicographically smallest reachable height sequence.

Level: Medium7 of 10
Topics: Topological sort, Segment tree, Heap
Solved: No attempts yet

Problem

Bessie is bored and is causing trouble in Farmer John's barn again. 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 the following:

If two adjacent stacks have heights that differ by at most $K$ ( $1\le K\le 10^9$ ), she can swap the two stacks.

What is the lexicographically smallest sequence of heights that Bessie can obtain after some sequence of these operations?

Input

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

Output

Print $N$ lines. The $i$ -th line contains the height of the $i$ -th haybale in the solution.

Hint

Bessie can swap the stacks 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

Examples1

Example 1
Input
```
5 3
7
7
3
6
2
```
Expected output
```
6
7
7
2
3
```