Problem Description

Little W gives you an integer array $x$ of length $n$. You need to construct an integer array $y$ of length $n$, and satisfy:

1. $\forall 1\le i,j,i+j\le n,y_{i+j}=y_i+y_j+k$, where $k$ is an integer that you must choose.
2. Minimize $d(x,y)=\sum\limits_{i=1}^n|x_i-y_i|$.
3. $-V\le y_i\le V$, where $V$ is a number given in the input.

Input Format

The first line contains two integers $n,V$.

The next line contains $n$ integers; the $i$-th integer represents $x_i$.

Output Format

The first line contains two integers $k,d$, representing the value you choose and your answer.

The next line contains $n$ integers; the $i$-th integer represents $y_i$.

It is guaranteed that the minimum value of $d$ fits in 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

Hint

Constraints

• 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}$.

For all testdata, it is guaranteed that $1\le n\le 10^7$, $|x_i|\le10^7$, $1\le V\le10^{12}$.

Notes about the Special Judge

For each test point:

If your output format is incorrect, you will get $0$ points.

If any number you output is not in the range $[-V,V]$, you will get $0$ points.

If your sequence $y$ does not match the $k$ you output, you will get $0$ points.

If your sequence $y$ does not match the $d$ you output, you will get $0$ points.

Otherwise, the score you get for this test point is $\max\{0,\min\{100,10100-\frac{10000d}{d'}\}\}$ percent of the total score for this test point, where $d'$ is the $d$ value of the best answer.

Translated by ChatGPT 5