AT_arc052_b [ARC052B] 円錐

[problemUrl]: https://atcoder.jp/contests/arc052/tasks/arc052_b 3次元空間( $ xyz $ 空間)上に $ N $ 個の円錐が互いに重なり合わないように浮いています。 どの円錐も底面が $ yz $ 平面と平行で、$ x $ 軸の正の方向にとがっています。 $ i $ 番目の円錐の底面の中心の $ x $ 座標の値は $ X_i $ で半径は $ R_i $ 、高さは $ H_i $ です。 以下のクエリに $ Q $ 個答えてください。 - $ 2 $ つの整数 $ A $ と $ B $ が与えられるので $ A\ ≦\ x\ ≦\ B $ となる空間の内いずれかの円錐の内側にある部分の体積をもとめよ。

入力は以下の形式で標準入力から与えられる。 > $ 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\ ≦\ 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 $