问题陈述

在三维空间（$xyz$ 空间）中，有 $N$ 个圆锥体浮在空中，彼此不重叠。

每个圆锥的底面与 $yz$ 平面平行，并且朝着 $x$ 轴正向尖锐。

第 $i$ 个圆锥底面中心的 $x$ 坐标是 $X_i$，半径是 $R_i$，高度是 $H_i$。

请回答以下查询共 $Q$ 个。

• 给定两个整数 $A$ 和 $B$，求位于空间内任一圆锥内部的部分的体积。

约束条件

• 所给数字均为整数
• $1 \leq N \leq 100$
• $1 \leq Q \leq 10^5$
• $0 \leq X_i \leq 10^4$
• $1 \leq H_i \leq 10^4$
• $1 \leq R_i \leq 10^3$
• $0 \leq A_i \leq B_i \leq 2 \times 10^4$

输入

输入以以下格式从标准输入读取。

$N$ $Q$ $X_1$ $R_1$ $H_1$ $X_2$ $R_2$ $H_2$ ： $X_N$ $R_N$ $H_N$ $A_1$ $B_1$ $A_2$ $B_2$ ： $A_Q$ $B_Q$

• 第一行包含两个整数，表示圆锥的数量 $N$ 和查询的数量 $Q$，以空格分隔。
• 第二行起的 $N$ 行中，第 $i$ 行包含圆锥底面中心的 $x$ 坐标 $X_i$、半径长度 $R_i$ 和高度 $H_i$，以空格分隔。
• 第 $N+2$ 行起的 $Q$ 行中，第 $i$ 行包含第 $i$ 个查询的内容，即两个整数 $A_i, B_i$，以空格分隔。

输出

输出共 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。输出末尾需要换行。如果输出的绝对误差或相对误差小于等于 $10^{-3}$ 则被接受。

示例1

10 10
3 3 3
2 1 1
5 2 3
1 5 6
2 9 3
4 6 12
11 18 5
4 15 25
0 2 3
1 1 7
0 1
0 2
0 10
3 10
0 100
3 8
1 5
2 9
3 4
6 9

输出示例1

8.843002
80.992182
4173.878112
3865.997282
8512.668894
2882.971997
1227.377293
3629.490541
114.081013
1747.545749

示例2

5 5
5 10 10
4 100 100
3 1000 1000
2 1000 1000
1 1000 1000
0 3
2 1000
4 314
3 217
5 432

输出示例2

9409079.422279
3139502408.531295
2100737789.465234
1613523459.243475
2532621914.444282