Union of Isosceles Right Triangles

You are given n isosceles right triangles. The i-th triangle is constructed with its right angle at point \((x_i, y_i)\) and its two legs extending upward and rightward with length \(m_i\). That is, the vertices of the triangle are \((x_i, y_i)\), \((x_i, y_i+m_i)\), and \((x_i+m_i, y_i)\).

Your task is to compute the total area covered by the union of these triangles.

Note

• The triangles may overlap. Make sure that overlapping regions are not counted more than once.
• The answer can be a fractional number.

inputFormat

The first line contains a single integer n (1 \(\leq\) n \(\leq\) 10⁵), the number of triangles.

Each of the next n lines contains three integers \(x_i\), \(y_i\), and \(m_i\) (\(0 \le x_i, y_i, m_i \le 10^9\)), representing the coordinates of the right angle and the leg length of the i-th triangle.

It is guaranteed that the input values are such that the answer does not have rounding issues when using standard double precision.

outputFormat

Output a single number, which is the total area covered by the union of the given triangles.

The answer will be considered correct if its absolute or relative error does not exceed \(10^{-6}\).

sample

1
0 0 1

0.5