喺一片遙遠嘅土地上，有一座堡壘。如果我哋用笛卡兒直角坐標系嚟表示方位，堡壘嘅領地可以睇成係一個以原點為圓心、半徑為 $R$ 嘅圓。堡壘領地嘅邊界被高牆圍住，由堡壘內部係睇唔到出面嘅。

堡壘入面有一啲建築物。為咗方便起見，建築物嘅邊界由 $n$ 個可能會重疊嘅長方形表示，呢啲長方形嘅邊平行於坐標軸。如果堡壘入面嘅一個點嚴格位於任何一個長方形嘅內部，呢個點就會被視為被遮擋（長方形邊界上面嘅點唔算喺內部）。

小 S 係呢座堡壘嘅守衛。佢企喺堡壘入面某個冇被遮擋嘅點 $(x, y)$ 嗰度。小 S 能夠守衛堡壘入面嘅另一個點 $(x', y')$，當且僅當線段 $(x, y) - (x', y')$ 上面嘅每一個點（包括兩個端點）都冇被遮擋。任務係計算小 S 能夠守衛嘅點集嘅面積，呢個面積代表咗小 S 可以監視嘅堡壘土地面積。

輸入格式

本題包含多個測試用例。輸入嘅第一行包含一個整數 $T$（$1 \le T \le 10^5$），表示測試用例嘅數量。

對於每個測試用例：

• 第一行包含兩個整數 $R, n$（$0 < R \le 10^6, 0 \le n \le 10^5$），分別表示堡壘嘅半徑同長方形嘅數量。
• 接落嚟嘅 $n$ 行，每行包含四個整數 $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)$ 表示右上角嘅坐標。保證所有長方形都嚴格位於堡壘領地內部，而且唔會接觸到領地邊界。
• 最後一行包含兩個整數 $x, y$（$|x|, |y| \le 10^6, x^2 + y^2 < R^2$），表示小 S 嘅坐標。保證點 $(x, y)$ 冇被遮擋。

保證所有測試用例入面 $n$ 嘅總和唔超過 $10^5$。

輸出格式

對於每個測試用例，輸出單行，包含一個實數，表示小 S 喺堡壘入面可以守衛嘅點集嘅面積。

如果同標準答案嘅相對或絕對誤差細過 $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

說明

對於第一個測試用例，對應嘅示意圖如下：

對於第二個測試用例，對應嘅示意圖如下：