Farmer John 的农场里有许多苹果树。每棵苹果树都有一个圆形区域，在炎热的夏天提供树荫。Farmer John 正在为他的奶牛建造一个围栏，并考虑了几个位置。对于每个围栏区域，他想知道该区域被树荫覆盖的百分比。

每个拟建的围栏区域形状为矩形，且边平行于坐标轴，由其左下角坐标以及区域的宽度和高度指定。请计算每个拟建的矩形围栏区域中被树荫覆盖的面积百分比。

输入格式

输入的第一行包含两个整数 $n$ ($1 \le n \le 3\,000$) 和 $q$ ($1 \le q \le 3\,000$)，其中 $n$ 是 Farmer John 果园中苹果树的数量，$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$)。每行描述一个 Farmer John 想要测试的矩形区域。该矩形的对角线从 $(x, y)$ 到 $(x + w, y + h)$。

输出格式

输出 $q$ 行，每行包含一个实数，表示该矩形区域中被树荫覆盖的百分比（范围为 0 到 100）。请按输入中矩形出现的顺序输出百分比。每个输出值与标准答案的相对误差或绝对误差应在 $10^{-5}$ 以内。

样例

输入 1

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

输出 1

100.000000000
89.536784729

输入 2

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

输出 2

87.222142378
98.586991373
57.862330458