Snuke 有一个白色的平面。她会依次进行 $n$ 次操作。在第 $i$ 次操作中，她会把圆心在 $(x_i, y_i)$、半径为 $r_i$ 的圆涂成黑色。

Takahashi 想要知道，每一次操作结束后，平面上黑色部分的面积是多少。

输入格式

从标准输入读入数据。

第一行输入一个整数 $T$，表示子任务编号。

第二行输入一个整数 $n$。

接下来 $n$ 行，第 $i + 1$ 行输入三个整数 $x_i, y_i, r_i$。

输出格式

输出到标准输出。

输出 $n$ 行，第 $i$ 行输出一个实数，表示第 $i$ 次操作结束后，平面上黑色部分的面积。

你的答案被判定为正确，当且仅当你每一行输出的答案与参考答案之间的绝对或相对误差小于 $10^{-9}$。

1
2
0 0 1
1 0 2

3.1415926536
12.5663706144

第一个圆的圆心在 $(0, 0)$，半径为 $1$，它的面积是 $\pi$。

第二个圆的圆心在 $(1, 0)$，半径为 $2$。它完全包含了第一个圆，所以这两个圆的并的面积是 $4 \pi$。

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

28.2743338823
40.8407044967
53.4070751110
53.4070751110
154.0763284686
282.6344779456

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

3.1415926536
5.0548156086
5.0548156086
6.8402137720
9.9818064256
9.9818064256

限制及约定

对于所有数据，保证：

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

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载