Problem Statement

3次元空間( $xyz$ 空間)上に $N$ 個の円錐が互いに重なり合わないように浮いています。

どの円錐も底面が $yz$ 平面と平行で、$x$ 軸の正の方向にとがっています。

$i$ 番目の円錐の底面の中心の $x$ 座標の値は $X_i$ で半径は $R_i$ 、高さは $H_i$ です。

以下のクエリに $Q$ 個答えてください。

• $2$ つの整数 $A$ と $B$ が与えられるので $A ≦ x ≦ B$ となる空間の内いずれかの円錐の内側にある部分の体積をもとめよ。

Constraints

• 与えられる数字はすべて整数
• $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$

Input

入力は以下の形式で標準入力から与えられる。

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$ が空白区切りで与えられる。

Output

出力は $Q$ 行からなる。 $i$ 行目には $i$ 番目のクエリの答えを $1$ 行で出力せよ。 出力は絶対誤差または相対誤差が $10^{-3}$ 以下であれば許容される。 なお、出力の末尾に改行を入れること。