Вы отправляетесь в путешествие на декартовой плоскости. Двигаясь из точки $(0, 0)$ в точку $(X, 0)$ с постоянной скоростью, вы будете осматривать достопримечательности. Достопримечательности моделируются как прямоугольники на плоскости с основанием в точке $(x_i, y_i)$, шириной $w_i$ и высотой $h_i$. К сожалению, достопримечательности могут перекрываться.

Расстояние от вас до достопримечательности — это евклидово расстояние от вас до ближайшей к вам точки этого прямоугольника. Достопримечательность считается «звездной» (Star Attraction), если расстояние от вас до нее является минимальным среди всех достопримечательностей. Если несколько достопримечательностей находятся на одинаковом минимальном расстоянии, «звездной» считается та, у которой меньше индекс (так как у нее лучше рейтинги).

Вы хотите узнать, какой процент времени каждая достопримечательность будет «звездной».

Входные данные

Первая строка содержит два целых числа $N$ и $X$ ($1 \le N \le 200\,000$, $1 \le X \le 1\,000\,000$).

Каждая из следующих $N$ строк содержит четыре целых числа $x_i, y_i, w_i$ и $h_i$ ($1 \le x_i, y_i \le 1\,000\,000$, $0 \le w_i, h_i \le 1\,000\,000$).

Выходные данные

Выведите $N$ строк. В $i$-й строке выведите процент времени, в течение которого $i$-я достопримечательность является «звездной». Ваш ответ будет считаться верным, если его абсолютная или относительная погрешность не превышает $10^{-8}$.

Примеры

Входные данные 1

2 10
1 2 5 1
2 1 1 5

Выходные данные 1

52.679491924
47.320508076

Входные данные 2

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

Выходные данные 2

53.571428571
35.714285714
10.714285714
0.000000000