Minimizing Haybales
Bessie is bored and yet again causing trouble in Farmer John's barn. FJ has N (1≤N≤105) stacks of haybales. For each i∈[1,N], the ith stack has hi (1≤hi≤109) 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≤109), 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.**
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≤100
- 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
Source: USA Computing Olympiad.
Input Format
The first line of input contains N and K. The i+1-st line contains the height of the i-th haybale.
Output Format
Please print out N lines, the i-th containing the height of the i-th haybale in the solution.