Unsatisfied with the usual Santa-tracking tools, Wesley has decided to make one of his own, called SantaTracker++!

Santa's entire trip can be modelled on the Cartesian plane. Santa's sleigh travels at a constant speed from ~(0, 0)~ to ~(X, 0)~. In addition, there are ~N~ rectangular-shaped houses (indexed from ~1~ to ~N~) of various sizes located on the plane. The ~i^\text{th}~ house can be modelled as a rectangle of width ~w_i~ and height ~h_i~ with its bottom left corner located at the coordinates ~(x_i, y_i)~. (Unfortunately due to poor planning, houses may overlap.)

Tracking Santa's movement is too unpredictable, so instead SantaTracker++ needs to predict which house he is currently located at. One known fact about Santa is that he will always deliver gifts to the house that is closest to his sleigh's position on the voyage interval. A house is considered to be closest if there is at least one point on the rectangle closer to the sleigh's current position than any other rectangle in Euclidean distance. In case of a tie in distance the house with the smaller index will be considered closer (these houses are more likely to house well-behaved kids).

For undisclosed reasons, Wesley needs to know which houses will Santa most likely end up at any point in the journey. For every house, find the percentage of Santa's trajectory where Santa's sleigh is closest to that house. As the lead developer of SantaTracker++, please help him out!

Constraints

For this problem, you will NOT be required to pass all the samples to receive points, and you are NOT required to pass all previous subtasks to receive points for a specific subtask.

For all subtasks:

~1 \le N \le 200\,000~
~1 \le X \le 10^6~
~1 \le x_i, y_i \le 10^6~
~0 \le w_i, h_i \le 10^6~

Subtask 1 [8%]

~1 \le N \le 500~
~w_i = h_i = 0~

Subtask 2 [18%]

~1 \le N \le 500~

Subtask 3 [33%]

~w_i = h_i = 0~

Subtask 4 [41%]

No additional constraints.

Input Specification

The first line will contain two integers ~N~ and ~X~, the number of houses and the length of the sleigh's trajectory.

The next ~N~ lines describe the houses on the Cartesian plane. Each line will contain ~4~ integers ~x_i~, ~y_i~, ~w_i~, ~h_i~, indicating the coordinates of the bottom left corner, the width, and the height of the rectangle respectively.

Output Specification

This problem is graded with a custom checker.

Output ~N~ lines, with the ~i^\text{th}~ line describing the percentage of the sleigh's trajectory where the ~i^\text{th}~ house is closest. Ensure that every line is terminated with a \n character and has no leading nor trailing spaces.

Your answer will be considered correct if it has an absolute or relative error of at most ~10^{-8}~ from the reference solution. It is guaranteed that the absolute or relative error of the reference solution is much smaller than ~10^{-8}~ from the optimal solution.

Sample Input 1

2 10
1 2 5 1
2 1 1 5

Sample Output 1

52.679491924
47.320508076

Sample Explanation 1

The sleigh will be closest to the first house for ~52.679491924\%~ of its journey and closest to the second house for the other ~47.320508076\%~.

Sample Input 2

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

Sample Output 2

53.571428571
35.714285714
10.714285714
0.000000000