在一片遙遠的土地上，有一座堡壘。如果我們用笛卡兒直角坐標系來表示方位，堡壘的領地可以看作是一個以原點為圓心、半徑為 $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

說明

對於第一組測試資料，對應的示意圖如下：

對於第二組測試資料，對應的示意圖如下：