問題文
3次元空間( xyz 空格)上方 N 圆锥体是浮动的,因此它们不会相互重叠。
每个圆锥体的底面是 yz 平行于平面,x 指向轴的正方向。
i 圆锥体底部中心 x 坐标值为 X_i 半径为 R_i ,高度为 H_i 。
对于以下查询 Q 请回答。 给出了
- 2 整数 A 和 B ,所以 求 A ≦ x ≦ B 空间内任意圆锥内部零件的体积。
制約
- 给出的所有数字均为整数
- 1 ≦ N ≦ 100
- 1 ≦ Q ≦ 10^5
- 0 ≦ X_i ≦ 10^4
- 1 ≦ H_i ≦ 10^4
- 1 ≦ R_i ≦ 10^3
- 0 ≦ A_i ≦ B_i ≦ 2×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
- 1 第 1 行是表示锥体数量的整数。 N 和一个表示查询数量的整数 Q 用空格分隔。
- 2 从线 N 行数过多 关于第 i 在线 一个整数,表示住在 i 圆锥体底部中心 x 表示坐标值的整数。 X_i 和代表半径长度的整数 R_i,表示高度的整数 一个整数,表示第 H_i 用空格分隔。
- N+2 从线 Q 行数过多 关于第 i 在线 一个整数,表示住在 i 个查询的内容 A_i, B_i 用空格分隔。
出力
输出是 第 Q 行组成。 i 在线 一个整数,表示住在 i 个查询的答案是 输出为 1 行。 输出有绝对或相对误差。 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