Problem Description

On a 2D plane, there is a line segment $L$ of length $d$, whose left endpoint is at the origin, and which lies on the $x$ axis. There are also $n$ segments $l_1, l_2, \cdots, l_n$ that are perpendicular to the $x$ axis, whose feet lie on segment $L$, and which are above the $x$ axis. For the $i$-th segment, its distance from the origin is $x_i$, and its length is $h_i$.

Besides segment $L$, the top endpoints of some segments have a negligible-sized light point installed, which can emit lasers to its left and right. A laser can only travel along a straight line, and it cannot pass through any segment (including segment $L$). We say a point $A$ on segment $L$ is covered if and only if there exists some light point such that it emits a laser in some direction and the laser finally lands on point $A$.

Now, compute the total length of all covered parts on segment $L$.

Please refer to the samples and sample explanations to better understand the statement.

Input Format

The first line contains two integers $n, d$, representing the number of segments other than segment $L$ and the length of segment $L$, respectively.

The next $n$ lines each contain three integers $op_i, x_i, h_i$, representing whether the top endpoint of the $i$-th segment has a light point, the distance of the $i$-th segment from the origin, and its length. Specifically, if $op_i = 0$, it means the top endpoint of the $i$-th segment has no light point; otherwise, it means the top endpoint has a light point.

Output Format

Output a real number, the total length of all covered parts on segment $L$. You must ensure that the relative error between your output and the standard answer does not exceed $10^{-3}$.

3 10
1 2 6
0 4 3
0 8 2

6.000000

5 15
0 4 3
1 5 5
1 6 6
0 9 2
0 10 3

8.500000

Hint

Sample 2 Explanation

The figure below corresponds to sample 2, where the bold parts are the uncovered areas.

Constraints and Limits

This problem uses bundled testdata. The score and special limits for each subtask are as follows:

• Subtask 1 (48 pts): $n \leqslant 10^3$.
• Subtask 2 (112 pts): no special limits.

For all testdata, $1 \leqslant n \leqslant 3 \times 10^5$, $1 \leqslant d \leqslant 10^9$, $op_i \in \{0, 1\}$, $0 \leqslant x_i \leqslant d$, $1 \leqslant h_i \leqslant 10^9$. It is guaranteed that $\forall i \neq j$, $x_i \neq x_j$. It is guaranteed that $x_i$ is strictly increasing.

Source

This problem is from COCI 2013-2014 CONTEST 3 T6 ODAŠILJAČI, and with the original data configuration, the full score is $160$ points.

Translated, organized, and provided by Eason_AC.

Translated by ChatGPT 5