#PU1188. USACO 2022 January Contest, Platinum — Problem 1. Minimizing Haybales

USACO 2022 January Contest, Platinum — Problem 1. Minimizing Haybales

USACO 2022 January Contest, Platinum — Problem 1. Minimizing Haybales

题目描述

Bessie is bored and yet again causing trouble in Farmer John's barn. FJ has NN (1≤N≤1051\leq N \leq 10^5) stacks of haybales. For each i∈[1,N]i\in [1,N], the iith stack has hih_i (1≤hi≤1091\le h_i\le 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 KK (1≤K≤1091\le K\le 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.

输入格式

The first line of input contains NN and KK. The i+1i+1-st line contains the height of the ii-th haybale.

输出格式

Please print out NN lines, the ii-th containing the height of the ii-th haybale in the solution.

数据范围

In 10% of all input cases, N≤100N\le 100 In another 20% of all input cases, N≤5000N\le 5000 In the remaining 70% of input cases, there are no additional Problem credits: Daniel Zhang and Benjamin Qi

样例

样例 1

5 3
7
7
3
6
2
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