VK Cup 2012 Round 2 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

sortings

two pointers

*2100

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Conveyor

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAnton came to a chocolate factory. There he found a working conveyor and decided to run on it from the beginning to the end.

The conveyor is a looped belt with a total length of 2*l* meters, of which *l* meters are located on the surface and are arranged in a straight line. The part of the belt which turns at any moment (the part which emerges from under the floor to the surface and returns from the surface under the floor) is assumed to be negligibly short.

The belt is moving uniformly at speed *v*_{1} meters per second. Anton will be moving on it in the same direction at the constant speed of *v*_{2} meters per second, so his speed relatively to the floor will be *v*_{1} + *v*_{2} meters per second. Anton will neither stop nor change the speed or the direction of movement.

Here and there there are chocolates stuck to the belt (*n* chocolates). They move together with the belt, and do not come off it. Anton is keen on the chocolates, but he is more keen to move forward. So he will pick up all the chocolates he will pass by, but nothing more. If a chocolate is at the beginning of the belt at the moment when Anton starts running, he will take it, and if a chocolate is at the end of the belt at the moment when Anton comes off the belt, he will leave it.

You are given the positions of the chocolates relative to the initial start position of the belt 0 ≤ *a*_{1} < *a*_{2} < ... < *a*_{n} < 2*l*. The positions on the belt from 0 to *l* correspond to the top, and from *l* to 2*l* — to the the bottom half of the belt (see example). All coordinates are given in meters.

Anton begins to run along the belt at a random moment of time. This means that all possible positions of the belt at the moment he starts running are equiprobable. For each *i* from 0 to *n* calculate the probability that Anton will pick up exactly *i* chocolates.

Input

The first line contains space-separated integers *n*, *l*, *v*_{1} and *v*_{2} (1 ≤ *n* ≤ 10^{5}, 1 ≤ *l*, *v*_{1}, *v*_{2} ≤ 10^{9}) — the number of the chocolates, the length of the conveyor's visible part, the conveyor's speed and Anton's speed.

The second line contains a sequence of space-separated integers *a*_{1}, *a*_{2}, ..., *a*_{n} (0 ≤ *a*_{1} < *a*_{2} < ... < *a*_{n} < 2*l*) — the coordinates of the chocolates.

Output

Print *n* + 1 numbers (one per line): the probabilities that Anton picks up exactly *i* chocolates, for each *i* from 0 (the first line) to *n* (the last line). The answer will be considered correct if each number will have absolute or relative error of at most than 10^{ - 9}.

Examples

Input

1 1 1 1

0

Output

0.75000000000000000000

0.25000000000000000000

Input

2 3 1 2

2 5

Output

0.33333333333333331000

0.66666666666666663000

0.00000000000000000000

Note

In the first sample test Anton can pick up a chocolate if by the moment he starts running its coordinate is less than 0.5; but if by the moment the boy starts running the chocolate's coordinate is greater than or equal to 0.5, then Anton won't be able to pick it up. As all positions of the belt are equiprobable, the probability of picking up the chocolate equals , and the probability of not picking it up equals .

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/20/2024 10:29:22 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|