Problem B
Mountain

DreamGrid is climbing a mountain. The mountain is described by a polyline on a 2D plane:

The region surrounded by the polyline and the x-axis denotes the mountain.

DreamGrid takes $n$ pictures at the points $(i, h_i)$ for each integer $i$ where $1 \le i \le n$. A picture covers a rectangle on the plane. Formally, a picture taken at $(i, h_i)$ covers all the points $(x, y)$ where $i - W \le x \le i + W$ and $h_i - H \le y \le h_i + H$.

However, his hard disk has limited space. When he saves the pictures into his hard disk, he can keep only $K$ pictures. He wants to maximize the total area of the mountain which is covered by at least one picture. You are asked to find the maximum area for $K = 1, 2, \cdots , n$.

The graph above is a sample where $n = 3, W = 1, H = 2$. The polyline describing the mountain is A-B-C-D-E. DreamGrid keeps $2$ pictures taken at C and D. The red area (polygon F-M-C-D-E-N-F) is the part of the mountain covered by the kept pictures.

Input

The first line of the input contains three integers $n, W$ and $H$ ($1 \le n \le 200$, $1 \le W \le 5$, $1 \le H \le 10\, 000$), indicating the number of points on the polyline and the size of the pictures.

The second line contains $n$ integers $h_1, h_2, \cdots , h_n$ ($1 \le h_i \le 10\, 000$), indicating the $y$ coordinates of the $n$ points on the polyline.

Output

Output $n$ lines, the $i$-th line contains a float number indicating the maximum area when $K = i$.

Your answer is acceptable if its absolute or relative error does not exceed $10^{-6}$.

Formally speaking, suppose that your output is $x$ and the jury’s answer is $y$. Your output is accepted if and only if $\frac{|x - y|}{\max (1, |y|)} \leq 10^{-6}$.

3 1 2
2 1 3

3.5000000000
4.5000000000
5.1666666667