题目描述

农夫约翰的农场里有许多苹果树。每棵苹果树都有一个圆形区域，在炎热的夏季提供树荫。农夫约翰打算为他的奶牛建造一个围栏，他已经选定了几个候选区域。对于每个拟围起来的区域，他想知道该区域中被树荫覆盖的面积百分比。

每个拟围起来的区域都是轴对齐的矩形，由其左下角坐标以及宽度和高度指定。请计算每个拟围矩形区域中被树荫覆盖的面积百分比。

输入格式

输入的第一行包含两个整数 $n$（$1 \le n \le 3{,}000$）和 $q$（$1 \le q \le 3{,}000$），其中 $n$ 是农夫约翰果园中苹果树的数量，$q$ 是他希望测试的矩形围栏区域的数量。

接下来 $n$ 行，每行包含三个整数 $x$、$y$（$-10^6 \le x, y \le 10^6$）和 $r$（$1 \le r \le 10^6$）。每行描述一棵树的圆形树荫区域，其中 $(x, y)$ 为圆心，$r$ 为半径。注意，树木的树干可能非常扭曲，因此两个树荫区域可能有相同的圆心，甚至可能完全相同。

接下来 $q$ 行，每行包含四个整数 $x$、$y$（$-10^6 \le x, y \le 10^6$）、$w$ 和 $h$（$1 \le w, h \le 10^6$）。每行描述农夫约翰希望测试的一个矩形区域。该矩形的对角线为从 $(x, y)$ 到 $(x + w, y + h)$。

输出格式

输出 $q$ 行，每行一个实数，表示该矩形中被树荫覆盖的面积百分比，取值范围为 $0$ 到 $100$。请按照输入中矩形的顺序输出对应的百分比。每个值的绝对误差或相对误差应不超过标准答案的 $10^{-5}$。

2 2
0 0 3
2 1 4
0 0 3 3
-3 -3 6 6

100
89.53678472917

4 3
-1 -1 3
1 -1 3
-1 1 3
1 1 3
-4 -4 8 8
-1 -4 2 8
-3 -1 12 3

87.2221423775645
98.5869913729161
57.8623304576387

提示

翻译由 DeepSeek V3.2 完成