Lexicographically Smallest Hay Bale Sequence

Bessie is causing mischief in Farmer John's barn! There are N hay bale piles, and the i-th pile has height \(h_i\). Bessie cannot knock over any pile, so the only allowed operation is to swap two adjacent piles if their heights differ by at most \(K\) (i.e. if \(|h_i-h_{i+1}|\le K\)).

During a sequence of such operations, Bessie wants to achieve the lexicographically smallest possible sequence of hay bale heights. However, there is a catch: if in the original order an earlier pile is too tall compared to a later pile ― more precisely, if for some i < j we have

[ h_i > h_j + K, ]

then these two piles carry an invariant: the i-th pile cannot be moved to the right of the j-th pile in any sequence of allowed moves. In other words, although Bessie can swap adjacent piles when their height difference is at most \(K\), she cannot swap two piles if doing so would force a very tall bale (by more than \(K\)) to overtake a much shorter one from the left.

Your task is to compute the lexicographically smallest height sequence that Bessie can achieve using any allowed sequence of swaps. The final sequence must be a permutation of the original heights and must respect the invariant: for every pair \(i<j\) in the original order with \(h_i > h_j+K\), the hay bale from position i must remain to the left of the bale from position j in the final arrangement.

Input Format: The first line contains two integers, \(N\) and \(K\). The second line contains \(N\) positive integers \(h_1,\, h_2,\, \dots,\, h_N\), the heights of the hay piles.

Note: \(1 \le N \le 10^5\), \(1 \le h_i \le 10^9\) and \(1 \le K \le 10^9\). It is guaranteed that the input is such that a sequence of allowed operations exists.

Output Format: Output a single line containing the lexicographically smallest sequence of hay bale heights (separated by spaces) that can be obtained by a sequence of allowed swaps.

Example

• Input:
  3 5
  10 1 6
• Output:
  6 10 1
• Explanation:

  Although swapping adjacent piles is only allowed when their heights differ by at most \(K\), Bessie can perform a series of moves. In the original order, since 10 and 1 differ by 9 (which is greater than 5), the invariant forces the pile of height 10 (at index 1) to remain to the left of the pile of height 1 (at index 2). However, the pile of height 6 (at index 3) can move arbitrarily with the other piles that do not have such a blocking constraint with it. The lexicographically smallest reachable sequence is [6, 10, 1].

inputFormat

The first line contains two integers \(N\) and \(K\). The second line contains \(N\) integers \(h_1, h_2, \dots, h_N\), separated by spaces.

outputFormat

Output one line with \(N\) integers – the lexicographically smallest sequence of hay bale heights that can be obtained by a series of allowed swaps.

sample

3 5
10 1 6

6 10 1