Vous faites un voyage dans le plan cartésien. En partant de $(0, 0)$ et en allant vers $(X, 0)$ à vitesse constante, vous observerez des attractions. Les attractions sont modélisées par des rectangles dans le plan, avec une base située en $(x_i, y_i)$, une largeur $w_i$ et une hauteur $h_i$. Malheureusement, les attractions peuvent se chevaucher.

La distance entre vous et une attraction est la distance euclidienne entre vous et le point le plus proche de cette attraction. Une attraction est considérée comme la « Star Attraction » si la distance entre vous et cette attraction est la plus petite parmi toutes les attractions. Si plusieurs attractions sont à la distance minimale, celle ayant l'indice le plus bas est la « Star Attraction » (elle a de meilleures notes).

Vous souhaitez savoir combien de temps chaque attraction sera la « Star Attraction », en pourcentage.

Entrée

La première ligne contient deux entiers, $N$ et $X$ ($1 \le N \le 200\,000$, $1 \le X \le 1\,000\,000$).

Chacune des $N$ lignes suivantes contient quatre entiers, $x_i$, $y_i$, $w_i$ et $h_i$ ($1 \le x_i, y_i \le 1\,000\,000$, $0 \le w_i, h_i \le 1\,000\,000$).

Sortie

Affichez $N$ lignes. Sur la $i$-ième ligne, affichez le pourcentage de temps pendant lequel la $i$-ième attraction est la « Star Attraction ». Votre réponse sera considérée comme correcte si son erreur absolue ou relative est au plus $10^{-8}$.

Exemples

Exemple 1

2 10
1 2 5 1
2 1 1 5

52.679491924
47.320508076

Exemple 2

4 7
1 3 0 0
3 4 0 0
5 5 0 0
3 4 0 0

53.571428571
35.714285714
10.714285714
0.000000000