A8924 | 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.

The first line contains four integers $n,q,a,b$ $(2<=n<=6000; 1<=q,a,b<=10^{9}; 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)$ .

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