你有一个非递减序列 x1, x2, ..., xn (1 ≤ x1 ≤ x2 ≤ ... ≤ xn ≤ q)。您还有两个整数 a 和 b (a ≤ b; a·(n - 1) < q)。
您的任务是将序列 x1, x2, ..., xn 转换为某个序列 y1, y2, ..., yn (1 ≤ yi ≤ q; a ≤ yi + 1 - yi ≤ b)。转换价格为以下总和:$$\sum_{i=1}^{n}(y_i - x_i)^2$$。您的任务是选择序列 y 来最小化所描述的转换价格。
输入
第一行包含四个整数 n、q、a、b (2 ≤ n ≤ 6000;1 ≤ q、a、b ≤ 109;a·(n - 1) < q;a ≤ b)。
第二行包含一个非递减整数序列 x1, x2, ..., xn (1 ≤ x1 ≤ x2 ≤ ... ≤ xn ≤ q)。
输出
在第一行中打印 n 个实数 — 所寻找的序列 y1, y2, ..., yn (1 ≤ yi ≤ q; a ≤ yi + 1 - yi ≤ b)。在第二行中打印最小转换价格,即 $$\sum_{i=1}^{n}(y_i - x_i)^2$$。
如果有多个最佳答案,您可以打印其中任何一个。
如果绝对或相对误差不超过 10 - 6,则答案将被视为正确。
示例
输入 #1
3 6 2 2 1 4 6
输出 #1
1.666667 3.666667 5.666667 0.666667
输入 #2
10 100000 8714 9344 3378 14705 17588 22672 32405 34309 37446 51327 81228 94982
输出 #2
1.000000 8715.000000 17429.000000 26143.000000 34857.000000 43571.000000 52285.000000 61629.000000 70973.000000 80317.000000 797708674.000000