Optimal Sequence Construction

You are given a monotonic non-decreasing sequence of n integers \(\{a_i\}\) and an integer \(k\). For every integer \(l \in [1, n]\), you need to construct a sequence \(\{b_{l,i}\}_{i=1}^l\) (note that the elements \(b_{l,i}\) are not necessarily integers) satisfying the condition:

\[ b_{l,i+1} \ge b_{l,i} + k, \quad \text{for all } 1 \le i < l, \]

and such that the difference measure \[ F(a, b, l) = \sum_{i=1}^l \left| a_i - b_{l,i} \right| \] is minimized for the prefix \(a_{[1\cdots l]} = \{a_1, a_2, \ldots, a_l\}\>.

Your task is to compute, for each \(l = 1, 2, \ldots, n\), the minimum possible value of \(F(a_{[1\cdots l]}, b_l, l)\) and output these values.

Note: It can be shown that an optimal sequence \(\{b_{l,i}\}\) can be obtained by projecting \(\{a_i\}\) onto the set of sequences satisfying \(b_{l,i+1} \ge b_{l,i} + k\). One effective method is to use a two‐pass greedy approach: first a forward pass to enforce a lower bound and then a backward pass to adjust accordingly.

inputFormat

The first line contains two numbers: an integer n (the length of the sequence) and an integer k.

The second line contains n space‐separated integers representing the sequence \(a_1, a_2, \ldots, a_n\) in non-decreasing order.

outputFormat

Output n numbers in one line. The \(i\)-th number should be the minimum possible value of \(F(a_{[1\cdots i]}, b_i, i)\) for the prefix of length i.

sample

3 5
2 3 10

0 4 6