DreamGrid 正在攀登一座山。这座山在二维平面上由一条折线描述： $(0, 0) - (1, h_1) - (2, h_2) - \dots - (n, h_n) - (n + 1, 0)$

由该折线与 $x$ 轴围成的区域即为这座山。

DreamGrid 在每个整数 $i$（$1 \le i \le n$）对应的点 $(i, h_i)$ 处拍摄了 $n$ 张照片。每张照片覆盖平面上的一个矩形区域。形式化地，在 $(i, h_i)$ 处拍摄的照片覆盖所有满足 $i - W \le x \le i + W$ 且 $h_i - H \le y \le h_i + H$ 的点 $(x, y)$。

然而，他的硬盘空间有限。当他将照片保存到硬盘时，最多只能保留 $K$ 张。他希望最大化被至少一张照片覆盖的山体总面积。你需要求出对于 $K = 1, 2, \dots, n$ 时的最大面积。

上图是一个 $n = 3, W = 1, H = 2$ 的样例。描述山体的折线为 A-B-C-D-E。DreamGrid 保留了在 C 和 D 处拍摄的 2 张照片。红色区域（多边形 F-M-C-D-E-N-F）即为被保留的照片所覆盖的山体部分。

输入格式

第一行包含三个整数 $n, W$ 和 $H$（$1 \le n \le 200, 1 \le W \le 5, 1 \le H \le 10\,000$），分别表示折线上的点数和照片的尺寸。

第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le 10\,000$），表示折线上 $n$ 个点的 $y$ 坐标。

输出格式

输出 $n$ 行，第 $i$ 行包含一个浮点数，表示当 $K = i$ 时的最大面积。

如果你的输出 $x$ 与标准答案 $y$ 满足 $\frac{|x - y|}{\max(1, |y|)} \le 10^{-6}$，则你的答案被视为正确。

样例

输入 1

3 1 2
2 1 3

输出 1

3.5000000000
4.5000000000
5.1666666667