Description

Given $N$ circles in the 2D Cartesian coordinate system. It is known that any two circles have no intersection points; that is, two circles are either disjoint or one contains the other. Compute the XOR area union of these circles.

The XOR area union is defined as follows: a region is counted if it lies inside an odd number of circles; otherwise, if it lies inside an even number of circles, it is not counted.

Input Format

The first line contains a positive integer $N$, the number of circles.

Each of the next $N$ lines contains $3$ integers $x,y,r$, representing a circle centered at $(x,y)$ with radius $r$.

Constraints: $|x_i|,|y_i|\le 10^8$, $0<r\leq 10^6$, $1\le N\le 2\times 10^5$.

Output Format

Output a single integer on one line: the result of the XOR area union of all circles divided by $\pi$.

2
0 0 1
0 0 2

3

Hint

Translated by ChatGPT 5