Attractions On Plane

You are going on a trip on the Cartesian plane. Starting at $(0, 0)$ and going to $(X, 0)$ at constant speed, you view attractions. Each attraction is a rectangle with its base at $(x_i, y_i)$, width $w_i$, and height $h_i$. Attractions can overlap.

The distance from you to an attraction is the Euclidean distance from you to its closest point. The attraction with the minimum distance is the Star Attraction. If several attractions share the minimum distance, the one with the lower index is the Star Attraction (it has the better rating).

For each attraction, find the percentage of the trip during which it is the Star Attraction.

The first line contains two integers $N$ and $X$ ($1 \le N \le 200000$, $1 \le X \le 1000000$).

Each of the next $N$ lines contains four integers $x_i$, $y_i$, $w_i$, and $h_i$ ($1 \le x_i, y_i \le 1000000$, $0 \le w_i, h_i \le 1000000$).

Output $N$ lines. On line $i$, print the percentage of time that attraction $i$ is the Star Attraction. An answer is accepted if its absolute or relative error is at most $10^{-8}$.