Wybierasz się w podróż po płaszczyźnie kartezjańskiej. Wyruszając z punktu $(0, 0)$ i zmierzając do $(X, 0)$ ze stałą prędkością, będziesz mijać atrakcje. Atrakcje są modelowane jako prostokąty na płaszczyźnie, z podstawą w punkcie $(x_i, y_i)$, szerokością $w_i$ oraz wysokością $h_i$. Niestety, atrakcje mogą na siebie nachodzić.

Odległość od Ciebie do atrakcji to odległość euklidesowa od Ciebie do najbliższego punktu tej atrakcji. Atrakcja jest „Gwiezdną Atrakcją” (Star Attraction), jeśli odległość od Ciebie do tej atrakcji jest minimalna spośród wszystkich atrakcji. Jeśli kilka atrakcji znajduje się w tej samej minimalnej odległości, Gwiezdną Atrakcją jest ta o niższym indeksie (ma lepsze oceny).

Chcesz wiedzieć, przez jaki procent czasu każda z atrakcji będzie Gwiezdną Atrakcją.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $N$ oraz $X$ ($1 \le N \le 200\,000$, $1 \le X \le 1\,000\,000$).

Każda z kolejnych $N$ linii zawiera cztery liczby całkowite $x_i, y_i, w_i$ oraz $h_i$ ($1 \le x_i, y_i \le 1\,000\,000$, $0 \le w_i, h_i \le 1\,000\,000$).

Wyjście

Wypisz $N$ linii. W $i$-tej linii wypisz procent czasu, przez który $i$-ta atrakcja jest Gwiezdną Atrakcją.

Twoja odpowiedź zostanie uznana za poprawną, jeśli jej błąd bezwzględny lub względny nie przekracza $10^{-8}$.

Przykład

Wejście 1

2 10
1 2 5 1
2 1 1 5

Wyjście 1

52.679491924
47.320508076

Wejście 2

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

Wyjście 2

53.571428571
35.714285714
10.714285714
0.000000000