题目描述

小 W 给了你一个长度为 $n$ 的整数数组 $x$。你需要构造一个长度也为 $n$ 的整数数组 $y$，并满足：

1. $\forall 1\le i,j,i+j\le n,y_{i+j}=y_i+y_j+k$，$k$ 是一个你需要钦定的整数。
2. $d(x,y)=\sum\limits_{i=1}^n|x_i-y_i|$ 最小。
3. $-V\le y_i\le V$，$V$ 是输入中给定的数。

输入格式

第一行两个整数 $n,V$。

接下来一行 $n$ 个整数，第 $i$ 个代表 $x_i$。

输出格式

第一行两个整数 $k,d$，代表你钦定的值和你的答案。

接下来一行 $n$ 个整数，第 $i$ 个代表 $y_i$。

题目保证 $d$ 的最小值在 long long 范围内。

5 10
2 3 8 5 4

-1 6
2 3 4 5 6

7 100
11 45 14 19 19 8 10

-17 51
16 15 14 13 12 11 10

提示

数据范围

• Subtask 1（$20$ pts）：$n\le10$，$V\le10$，$|x_i|\le10$；
• Subtask 2（$20$ pts）：$n\le100$，$|x_i|\le100$，$V\le1000$；
• Subtask 3（$20$ pts）：$n\le10^6$，$|x_i|\le10^6$，$V=10^{12}$；
• Subtask 4（$20$ pts）：$n\le10^7$，$|x_i|\le10^7$，$V\le10^7$;
• Subtask 5（$20$ pts）：$n\le10^7$，$|x_i|\le10^7$，$V\le 10^{12}$。

对于所有数据，保证 $1\le n\le 10^7$，$|x_i|\le10^7$，$1\le V\le10^{12}$。

关于 Special Judge 的说明

对于每个测试点：

如果你输出的格式不正确，你将会获得 $0$ 分。

如果你输出的数中有不在 $[-V,V]$ 范围的数，你将会获得 $0$ 分。

如果你的数列 $y$ 不符合你输出的 $k$，你将会获得 $0$ 分。

如果你的数列 $y$ 不符合你输出的 $d$，你将会获得 $0$ 分。

否则你将会获得的分数为该测试点总分的百分之 $\max\{0,\min\{100,10100-\frac{10000d}{d'}\}\}$，$d'$ 是答案的 $d$ 值。