You've got a non-decreasing sequence x₁, x₂, ..., x_n (1 ≤ x₁ ≤ x₂ ≤ ... ≤ 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₁, x₂, ..., x_n into some sequence y₁, y₂, ..., y_n (1 ≤ y_i ≤ q; a ≤ y_i + 1 - y_i ≤ b). The transformation price is the following sum: $\text{[math]}$ . 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⁹; a·(n - 1) < q; a ≤ b).

The second line contains a non-decreasing integer sequence x₁, x₂, ..., x_n (1 ≤ x₁ ≤ x₂ ≤ ... ≤ x_n ≤ q).

Output

In the first line print n real numbers — the sought sequence y₁, y₂, ..., y_n (1 ≤ y_i ≤ q; a ≤ y_i + 1 - y_i ≤ b). In the second line print the minimum transformation price, that is, $\text{[math]}$ .

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.

Sequence Transformation

Examples