I ett avlägset land ligger en fästning. Om vi representerar orienteringen med ett kartesiskt koordinatsystem kan fästningens territorium betraktas som en cirkel med medelpunkt i origo och radie $R$. Gränsen för fästningens territorium omges av höga murar, och det är omöjligt att se utsidan inifrån fästningen.

Inuti fästningen finns några byggnader. För enkelhetens skull representeras byggnadernas gränser av $n$ eventuellt överlappande rektanglar vars sidor är parallella med koordinataxlarna. En punkt inuti fästningen anses vara blockerad om den ligger strikt inuti någon av rektanglarna (punkter på rektanglarnas rand anses inte ligga inuti).

Little S är en vakt i denna fästning. Han står i någon oblockerad punkt $(x, y)$ inuti fästningen. Little S kan bevaka en annan punkt $(x', y')$ inuti fästningen om och endast om varje punkt på linjesegmentet $(x, y) - (x', y')$ (inklusive de två ändpunkterna) är oblockerad. Uppgiften är att beräkna arean av den mängd punkter som Little S kan bevaka, vilket representerar arean av den fästningsmark som Little S kan överblicka.

Indata

Detta problem innehåller flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 10^5$), som anger antalet testfall.

För varje testfall:

• Den första raden innehåller två heltal $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$), som representerar fästningens radie och antalet rektanglar.
• De följande $n$ raderna innehåller var och en fyra heltal $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$), som beskriver en rektangel, där $(x_1, y_1)$ representerar koordinaterna för det nedre vänstra hörnet och $(x_2, y_2)$ representerar koordinaterna för det övre högra hörnet. Det garanteras att alla rektanglar ligger strikt inom fästningens territorium och inte vidrör territoriets gräns.
• Den sista raden innehåller två heltal $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$), som representerar koordinaterna för Little S. Det garanteras att punkten $(x, y)$ inte är blockerad.

Det garanteras att den totala summan av $n$ över alla testfall inte överstiger $10^5$.

Utdata

För varje testfall, skriv ut en enda rad med ett reellt tal som representerar arean av den mängd punkter som Little S kan bevaka inom fästningen.

Svaret betraktas som korrekt om det relativa eller absoluta felet jämfört med standardsvar är mindre än $10^{-6}$. Med andra ord, om din utdata är $a$ och standardsvar är $b$, betraktas din utdata som korrekt om och endast om $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$.

Exempel

Indata

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

Utdata

5.598332050807308
513.142778328943998

Anmärkning

För det första testfallet ser motsvarande bild ut så här:

För det andra testfallet ser motsvarande bild ut så här: