問題文

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$ 行目には円錐の個数を表す整数 $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