Bessie is bored and yet again causing trouble in Farmer John's barn. FJ has N (1≤N≤10^5) stacks of haybales. For each i∈[1,N], the ith stack has hi (1≤hi≤10^9) haybales. Bessie does not want any haybales to fall, so the only operation she can perform is as follows:
If two adjacent stacks' heights differ by at most K (1≤K≤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≤10^0
In another 20% of all input cases, N≤5000
In the remaining 70% of input cases, there are no additional constraints
Problem credits: Daniel Zhang and Benjamin Qi