I et fjernt land ligger det en festning. Hvis vi representerer orienteringen ved hjelp av et kartesisk koordinatsystem, kan festningens territorium betraktes som en sirkel med sentrum i origo og radius $R$. Grensen til festningens territorium er omgitt av høye murer, og det er umulig å se utsiden fra innsiden av festningen.

Inne i festningen er det noen bygninger. For enkelhets skyld er bygningenes grenser representert ved $n$ muligens overlappende rektangler med sider som er parallelle med koordinataksene. Et punkt inne i festningen regnes som blokkert hvis det ligger strengt inne i et av rektanglene (punkter på randen av rektanglene regnes ikke som å ligge på innsiden).

Little S er en vakt i denne festningen. Han står i et ublokkert punkt $(x, y)$ inne i festningen. Little S kan vokte et annet punkt $(x', y')$ inne i festningen hvis og bare hvis hvert punkt på linjestykket $(x, y) - (x', y')$ (inkludert de to endepunktene) ikke er blokkert. Oppgaven er å beregne arealet av mengden av punkter som Little S kan vokte, noe som representerer arealet av festningsområdet som Little S kan holde oppsyn med.

Inndata

Denne oppgaven inneholder flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 10^5$), som angir antallet testtilfeller.

For hvert testtilfelle:

• Den første linjen inneholder to heltall $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$), som representerer festningens radius og antallet rektangler.
• De neste $n$ linjene inneholder hver fire heltall $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 et rektangel, der $(x_1, y_1)$ representerer koordinatene til det nederste venstre hjørnet og $(x_2, y_2)$ representerer koordinatene til det øverste høyre hjørnet. Det garanteres at alle rektanglene ligger strengt innenfor festningens territorium og ikke berører grensen til territoriet.
• Den siste linjen inneholder to heltall $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$), som representerer koordinatene til Little S. Det garanteres at punktet $(x, y)$ ikke er blokkert.

Det garanteres at den totale summen av $n$ over alle testtilfeller ikke overstiger $10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje med et reelt tall som representerer arealet av mengden av punkter som Little S kan vokte inne i festningen.

Svaret vil bli regnet som riktig hvis den relative eller absolutte feilen sammenlignet med fasitsvaret er mindre enn $10^{-6}$. Med andre ord, hvis utdataene dine er $a$ og fasitsvaret er $b$, regnes svaret ditt som riktig hvis og bare hvis $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$.

Eksempel

Inndata

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

Merk

For det første testtilfellet er det tilhørende bildet som følger:

For det andre testtilfellet er det tilhørende bildet som følger: