Í fjarlægu landi er virki. Ef við táknum afstöðuna með kartesísku hnitakerfi má líta á yfirráðasvæði virkisins sem hring með miðju í upphafspunkti og geisla $R$. Mörk yfirráðasvæðis virkisins eru umkringd háum múrum og ómögulegt er að sjá út fyrir virkið innan úr því.

Inni í virkinu eru nokkrar byggingar. Til hægðarauka eru mörk bygginganna táknuð með $n$ rétthyrningum sem geta skarast og hafa hliðar samsíða hnitakerfisásunum. Punktur inni í virkinu telst hulinn ef hann liggur strangt inni í einhverjum rétthyrninganna (punktar á jaðri rétthyrninganna teljast ekki vera inni í þeim).

Little S er vörður í þessu virki. Hann stendur í einhverjum óhuldum punkti $(x, y)$ inni í virkinu. Little S getur vaktað annan punkt $(x', y')$ inni í virkinu þá og því aðeins að sérhver punktur á strikinu $(x, y) - (x', y')$ (þar með taldir báðir endapunktarnir) sé óhulinn. Verkefnið er að reikna flatarmál mengis þeirra punkta sem Little S getur vaktað, sem táknar flatarmál þess lands í virkinu sem Little S getur haft yfirsýn yfir.

Inntak

Þetta verkefni inniheldur mörg prófunartilvik. Fyrsta lína inntaksins inniheldur heiltölu $T$ ($1 \le T \le 10^5$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik:

• Fyrsta línan inniheldur tvær heiltölur $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$), sem tákna geisla virkisins og fjölda rétthyrninga.
• Næstu $n$ línur innihalda hver um sig fjórar heiltölur $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$), sem lýsa rétthyrningi, þar sem $(x_1, y_1)$ táknar hnit neðra vinstra hornsins og $(x_2, y_2)$ táknar hnit efra hægra hornsins. Tryggt er að allir rétthyrningarnir liggi strangt innan yfirráðasvæðis virkisins og snerti ekki mörk svæðisins.
• Síðasta línan inniheldur tvær heiltölur $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$), sem tákna hnit Little S. Tryggt er að punkturinn $(x, y)$ sé ekki hulinn.

Tryggt er að heildarsumma $n$ yfir öll prófunartilvik fari ekki yfir $10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu með rauntölu sem táknar flatarmál mengis þeirra punkta sem Little S getur vaktað innan virkisins.

Svarið telst rétt ef hlutfallsleg eða algild skekkja miðað við rétt svar er minni en $10^{-6}$. Með öðrum orðum, ef úttakið þitt er $a$ og rétta svarið er $b$, þá telst úttakið þitt rétt þá og því aðeins að $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$.

Dæmi

Inntak

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

Úttak

5.598332050807308
513.142778328943998

Athugasemd

Fyrir fyrsta prófunartilvikið er samsvarandi mynd sem hér segir:

Fyrir annað prófunartilvikið er samsvarandi mynd sem hér segir: