CF280E.Sequence Transformation

You've got a non-decreasing sequence _x_1, _x_2, ..., x__n (1 ≤ _x_1 ≤ _x_2 ≤ ... ≤ x__n ≤ q). You've also got two integers a and b (a ≤ b; a·(n - 1) < q).

Your task is to transform sequence _x_1, _x_2, ..., x__n into some sequence _y_1, _y_2, ..., y__n (1 ≤ y__i ≤ q; a ≤ y__i + 1 - y__i ≤ b). The transformation price is the following sum: . Your task is to choose such sequence y that minimizes the described transformation price.

你有一个非递减序列 $x_1, x_2, \dots, x_n$（满足 $1 \le x_1 \le x_2 \le \dots \le x_n \le q$）。你还拥有两个整数 $a$ 和 $b$（满足 $a \le b$ 且 $a \cdot (n - 1) < q$）。

你的任务是将序列 $x_1, x_2, \dots, x_n$ 变换为某个序列 $y_1, y_2, \dots, y_n$，使其满足：

• 对所有 $i$，有 $1 \le y_i \le q$；
• 对所有 $i = 1, 2, \dots, n-1$，有 $a \le y_{i+1} - y_i \le b$。

该变换的代价定义为如下和式：

你的任务是选择满足上述约束的序列 $y$，使得该变换代价最小。

The first line contains four integers n, q, a, b (2 ≤ n ≤ 6000; 1 ≤ q, a, b ≤ 109; a·(n - 1) < q; a ≤ b).

The second line contains a non-decreasing integer sequence _x_1, _x_2, ..., x__n (1 ≤ _x_1 ≤ _x_2 ≤ ... ≤ x__n ≤ q).

第一行包含四个整数 $n$、$q$、$a$、$b$（$2 \le n \le 6000$；$1 \le q, a, b \le 10^9$；$a\cdot(n - 1) < q$；$a \le b$）。

第二行包含一个非递减的整数序列 $x_1, x_2, ..., x_n$（$1 \le x_1 \le x_2 \le ... \le x_n \le q$）。

In the first line print n real numbers — the sought sequence _y_1, _y_2, ..., y__n (1 ≤ y__i ≤ q; a ≤ y__i + 1 - y__i ≤ b). In the second line print the minimum transformation price, that is, .

If there are multiple optimal answers you can print any of them.

The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

第一行输出 $n$ 个实数——所求序列 $y_1,\ y_2,\ \dots,\ y_n$（满足 $1 \le y_i \le q$；且 $a \le y_{i+1} - y_i \le b$）。
第二行输出最小变换代价，即 。

若存在多个最优解，输出任意一个即可。

当答案的绝对误差或相对误差不超过 $10^{-6}$ 时，即视为正确。