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

Note 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

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