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.

Input

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*)$.

Output

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