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 ≤ 109; a·(n - 1) q; a ≤ b).The second line contains a non-decreasing integer sequence x1, x2, ..., xn(1 ≤ x1 ≤ x2 ≤ ... ≤ xn ≤ q).

输出描述:

In the first line print n real numbers — the sought sequence y1, y2, ..., yn(1 ≤ yi ≤ q; a ≤ yi + 1 - yi ≤ 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.