Problem Description

Given a non-decreasing integer sequence $\{a_i\}$ of length $n$ and an integer $k$.

We define the "difference degree" $F(x,y,p)$ between two sequences $\{x_i\}$ and $\{y_i\}$ of length $p$ as $F(x,y,p)=\sum_{i=1}^p |x_i-y_i|$.

For each integer $l \in [1,n]$, you need to construct a sequence $\{b_{l,i}\}$ of length $l$. This sequence must satisfy that for any $1\le i < l$, $b_{l,i+1}\ge b_{l,i}+k$; and $F(a_{[1\cdots l]},b_l,l)$ is minimized. Here, $a_{[1\cdots l]}$ represents the prefix of $\{a_i\}$ of length $l$, i.e., $\{a_1,a_2,\cdots,a_l\}$. Note that $b_{l,i}$ does not necessarily have to be an integer.

Input Format

The first line contains two integers $n, k$.
The second line contains $n$ integers representing $\{a_i\}$.
The third line contains an integer $T$, which indicates the output format. Refer to the "Output Format" for specific explanations.

Output Format

• If $T=0$, output $n$ integers, each on a new line. The $l$-th line should contain the integer $F(a_{[1\cdots l]},b_l,l)$.
• If $T=1$, output a single integer on one line, representing $F(a,b_n,n)$.

Sample Input and Output

Sample Input #1

5 2
2 3 4 5 6
0

Sample Output #1

0
1
2
4
6

Sample Input #2

6 2
1 1 4 5 6 8
0

Sample Output #2

0
2
2
3
4
5

Sample Input #3

6 2
1 1 4 5 6 8
1

Sample Output #3

5

Sample Input #4

20 4
4 6 7 9 19 21 30 32 33 35 49 50 58 67 75 77 78 89 91 91
0

Sample Output #4

0
2
5
10
10
12
12
14
17
22
22
25
25
25
25
27
30
30
32
36

Notes

Sample Explanation

Sample #1

One possible construction scheme is:

$$ \begin{aligned} b_1&=\{2\}\\ b_2&=\{2,4\}\\ b_3&=\{1,3,5\}\\ b_4&=\{1,3,5,7\}\\ b_5&=\{0,2,4,6,8\}\\ \end{aligned} $$

Sample #2

One possible construction scheme is:

$$ \begin{aligned} b_1&=\{1\}\\ b_2&=\{0,2\}\\ b_3&=\{0,2,4\}\\ b_4&=\{0,2,4,6\}\\ b_5&=\{-1,1,3,5,7\}\\ b_6&=\{-1,1,3,5,7,9\}\\ \end{aligned} $$

Sample #3

Similar to Sample #2, but since $T=1$, you only need to output $F(a,b_6,6)=5$.

Data Range and Constraints

$$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|} \hline \textbf{subtask} & \textbf{score} & \bm{{n\le}} & \bm{{T=}} & \bm{{k,a_i\le}} & \textbf{subtask dependency}\cr\hline 1 & 30 & 100 & 0 & 100 & -\cr\hline 2 & 30 & 10^5 & 0 & 10^6 & 1\cr\hline 3 & 40 & 10^6 & 1 & 10^6 & -\cr\hline \end{array} $$

For $100\%$ of the data, $1\le n \le 10^6$, $1\le k,a_i\le 10^6$, $T\in\{0,1\}$.

见题面 Input 部分

见题面 Output 部分