Given $n$ circles in a Cartesian coordinate system. It is known that no two circles intersect, meaning the relationship between any two circles is either disjoint or one is contained within the other. Calculate the XOR area union of these circles.
The XOR area union is defined as follows: a region is included in the area calculation if it lies within an odd number of circles, and it is ignored if it lies within an even number of circles.
Input
The first line contains a positive integer $n$, representing the number of circles.
The next $n$ lines each contain three non-negative integers $x, y, r$, representing a circle with center $(x, y)$ and radius $r$. It is guaranteed that $|x|, |y|, r \le 10^8$ and $r > 0$.
Output
Output a single integer representing the result of the XOR area union of all circles divided by $\pi$.
Examples
Input 1
2 0 0 1 0 0 2
Output 1
3
Subtasks
| Test Case ID | $N$ |
|---|---|
| 1~3 | $\le 5000$ |
| 4~6 | $\le 30000$ |
| 7~10 | $\le 200000$ |