Kaukaisessa maassa on linnoitus. Jos esitämme suunnat karteesisen koordinaatiston avulla, linnoituksen alue voidaan nähdä origokeskisenä ympyränä, jonka säde on $R$. Linnoituksen alueen rajaa ympäröivät korkeat muurit, eikä linnoituksen sisältä ole mahdollista nähdä ulos.

Linnoituksen sisällä on joitakin rakennuksia. Mukavuuden vuoksi rakennusten rajat esitetään $n$:llä mahdollisesti päällekkäisellä suorakulmiolla, joiden sivut ovat koordinaattiakselien suuntaisia. Linnoituksen sisällä olevan pisteen katsotaan olevan estetty, jos se sijaitsee aidosti jonkin suorakulmion sisäpuolella (suorakulmioiden reunalla olevia pisteitä ei katsota sisäpuolella oleviksi).

Little S on tämän linnoituksen vartija. Hän seisoo jossakin estämättömässä pisteessä $(x, y)$ linnoituksen sisällä. Little S voi vartioida toista linnoituksen sisällä olevaa pistettä $(x', y')$jos ja vain jos jokainen janan $(x, y) - (x', y')$ piste (mukaan lukien molemmat päätepisteet) on estämätön. Tehtävänä on laskea niiden pisteiden joukon pinta-ala, joita Little S voi vartioida, mikä kuvaa sitä linnoituksen maa-alaa, jota Little S pystyy valvomaan.

Syöte

Tässä tehtävässä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^5$), joka ilmaisee testitapausten lukumäärän.

Jokaiselle testitapaukselle:

• Ensimmäinen rivi sisältää kaksi kokonaislukua $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$), jotka ilmaisevat linnoituksen säteen ja suorakulmioiden lukumäärän.
• Seuraavat $n$ riviä sisältävät kukin neljä kokonaislukua $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$), jotka kuvaavat suorakulmion, missä $(x_1, y_1)$ ilmaisee vasemman alakulman koordinaatit ja $(x_2, y_2)$ ilmaisee oikean yläkulman koordinaatit. On taattu, että kaikki suorakulmiot sijaitsevat aidosti linnoituksen alueen sisällä eivätkä kosketa alueen rajaa.
• Viimeinen rivi sisältää kaksi kokonaislukua $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$), jotka ilmaisevat Little S:n koordinaatit. On taattu, että piste $(x, y)$ ei ole estetty.

On taattu, että lukujen $n$ kokonaissumma yli kaikkien testitapausten ei ylitä arvoa $10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää reaaliluvun: sen pistejoukon pinta-alan, jota Little S voi linnoituksen sisällä vartioida.

Vastaus katsotaan oikeaksi, jos suhteellinen tai absoluuttinen virhe verrattuna mallivastaukseen on pienempi kuin $10^{-6}$. Toisin sanoen, jos tulosteesi on $a$ ja mallivastaus on $b$, tulosteesi katsotaan oikeaksi jos ja vain jos $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$.

Esimerkki

Syöte

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

Tuloste

5.598332050807308
513.142778328943998

Huomautus

Ensimmäistä testitapausta vastaava kuva on seuraava:

Toista testitapausta vastaava kuva on seuraava: