Snuke has a white plane. She performs $n$ operations in sequence. In the $i$-th operation, she paints a circle with center $(x_i, y_i)$ and radius $r_i$ black.

Takahashi wants to know the area of the black region on the plane after each operation.

Input

The input is read from standard input.

The first line contains an integer $T$, representing the subtask number.

The second line contains an integer $n$.

The next $n$ lines each contain three integers $x_i, y_i, r_i$.

Output

Output to standard output.

Output $n$ lines, where the $i$-th line contains a real number representing the area of the black region on the plane after the $i$-th operation.

Your answer is considered correct if and only if the absolute or relative error between your output and the reference answer is less than $10^{-9}$.

Constraints

For all test cases, it is guaranteed that:

• $1 \le n \le 2000$
• $-10^4 < x_i, y_i < 10^4$
• $0 < r_i < 10^4$

Subtasks

Examples

Input 1

1
2
0 0 1
1 0 2

Output 1

3.1415926536
12.5663706144

Explanation 1

The first circle has its center at $(0, 0)$ and radius $1$, so its area is $\pi$.

The second circle has its center at $(1, 0)$ and radius $2$. It completely contains the first circle, so the area of the union of these two circles is $4 \pi$.

Input 2

2
6
-9 -6 3
9 -2 2
0 -1 2
0 -1 2
10 -6 6
-3 -7 7

Output 2

28.2743338823
40.8407044967
53.4070751110
53.4070751110
154.0763284686
282.6344779456

Explanation 2

The circles are added one by one. The area of the union of the circles is calculated after each operation. Note that some circles may be identical or completely contained within others.

Input 3

3
6
2 10 1
1 10 1
2 10 1
2 9 1
4 8 1
4 8 1

Output 3

3.1415926536
5.0548156086
5.0548156086
6.8402137720
9.9818064256
9.9818064256

Explanation 3

Similar to Example 2, the area is updated incrementally. Duplicate circles do not increase the total area.