遠い大地に一つの要塞があります。デカルト座標系を用いて位置を表すと、要塞の領地は原点を中心とする半径 $R$ の円とみなすことができます。要塞の領地の境界は高い壁に囲まれており、要塞の内部から外部を見ることはできません。

要塞の内部にはいくつかの建物があります。便宜上、建物の境界は座標軸に平行な辺を持つ、重なり合う可能性のある $n$ 個の長方形で表されます。要塞内部の点は、いずれかの長方形の内部に厳密に含まれている場合、遮蔽されているとみなされます（長方形の境界上の点は内部にあるとはみなされません）。

Little S はこの要塞の衛兵です。彼は要塞内部の遮蔽されていないある点 $(x, y)$ に立っています。Little S が要塞内部の別の点 $(x', y')$ を警備できるのは、線分 $(x, y) - (x', y')$ 上のすべての点（両端点を含む）が遮蔽されていない場合、かつその場合に限ります。あなたの仕事は、Little S が警備できる点の集合の面積、すなわち Little S が見渡せる要塞の土地の面積を計算することです。

入力

この問題には複数のテストケースが含まれます。入力の 1 行目には、テストケースの個数を表す整数 $T$（$1 \le T \le 10^5$）が与えられます。

各テストケースについて：

• 1 行目には、要塞の半径と長方形の個数を表す 2 つの整数 $R, n$（$0 < R \le 10^6, 0 \le n \le 10^5$）が与えられます。
• 続く $n$ 行には、それぞれ長方形を表す 4 つの整数 $x_1, y_1, x_2, y_2$（$|x_1|, |x_2|, |y_1|, |y_2| \le 10^6, x_1 < x_2, y_1 < y_2$）が与えられます。ここで $(x_1, y_1)$ は左下の頂点の座標、$(x_2, y_2)$ は右上の頂点の座標を表します。すべての長方形は要塞の領地内部に厳密に含まれており、領地の境界には接しないことが保証されます。
• 最後の行には、Little S の座標を表す 2 つの整数 $x, y$（$|x|, |y| \le 10^6, x^2 + y^2 < R^2$）が与えられます。点 $(x, y)$ は遮蔽されていないことが保証されます。

すべてのテストケースにおける $n$ の総和は $10^5$ を超えないことが保証されます。

出力

各テストケースについて、Little S が要塞内で警備できる点の集合の面積を表す実数を 1 行に出力してください。

想定解との相対誤差または絶対誤差が $10^{-6}$ 以下の場合、出力は正解とみなされます。すなわち、あなたの出力を $a$、想定解を $b$ としたとき、$\frac{|a-b|}{\max(1,b)} \le 10^{-6}$ を満たす場合かつその場合に限り正解と判定されます。

入出力例

入力

2
2 3
-1 -1 0 0
-1 -1 0 1
0 -1 1 0
1 1
26 5
-3 -23 10 21
-15 3 -5 14
-12 -18 -10 -15
-5 -6 -2 8
7 -23 10 -19
-10 0

出力

5.598332050807308
513.142778328943998

注記

1 番目のテストケースに対応する図は以下の通りです：

2 番目のテストケースに対応する図は以下の通りです：