题目描述

给出一个长度为 $n$ 的单调不降整数数列 $\{a_i\}$ 和一个整数 $k$。

我们定义两个长度均为 $p$ 的序列 $\{x_i\},\{y_i\}$ 的「差异度」$F(x,y,p)=\sum_{i=1}^p |x_i-y_i|$。

现在对于每个整数 $l \in [1,n]$，你都需要构造一个长度为 $l$ 的序列 $\{b_{l,i}\}$。满足对于任意 $1\le i <l$，$b_{l,i+1}\ge b_{l,i}+k$；且 $F(a_{[1\cdots l]},b_l,l)$ 最小。其中 $a_{[1\cdots l]}$ 表示 $\{a_i\}$ 的长度为 $l$ 的前缀，即 $\{a_1,a_2,\cdots,a_l\}$。注意，$b_{l,i}$ 没必要是整数。

输入格式

第一行输入两个整数 $n,k$。
第二行输入 $n$ 个整数，代表 $\{a_i\}$。
第三行输入一个整数 $T$，代表答案输出方式。具体解释请参考「输出格式」。

输出格式

• 若 $T=0$，则输出 $n$ 个整数，每个整数单独占一行。第 $l$ 行的整数代表 $F(a_{[1\cdots l]},b_l,l)$。
• 若 $T=1$，则你仅需输出一行一个整数，表示 $F(a,b_n,n)$。

5 2
2 3 4 5 6
0

0
1
2
4
6

6 2
1 1 4 5 6 8
0

0
2
2
3
4
5

6 2
1 1 4 5 6 8
1

5

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

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

提示

样例解释

样例 #1

如下是一种可能的构造方案：

$$\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} $$

样例 #2

如下是一种可能的构造方案：

$$\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} $$

样例 #3

同样例 #2，只不过 $T=1$，你只需要输出 $F(a,b_6,6)=5$ 即可。

数据范围及约定

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|} \hline \textbf{subtask} & \textbf{分值} & \bm{{n\le}} & \bm{{T=}} & \bm{{k,a_i\le}} & \textbf{subtask 依赖}\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} $$

对于 $100\%$ 的数据，$1\le n \le 10^6$，$1\le k,a_i\le 10^6$，$T\in\{0,1\}$。