In einem fernen Land steht eine Festung. Wenn wir die Lage mithilfe eines kartesischen Koordinatensystems darstellen, kann das Gebiet der Festung als Kreis mit Mittelpunkt im Ursprung und Radius $R$ betrachtet werden. Die Grenze des Festungsgebiets ist von hohen Mauern umgeben, und es ist unmöglich, vom Inneren der Festung nach draußen zu sehen.

Innerhalb der Festung befinden sich einige Gebäude. Der Einfachheit halber werden die Grenzen der Gebäude durch $n$ sich möglicherweise überlappende Rechtecke dargestellt, deren Kanten parallel zu den Koordinatenachsen verlaufen. Ein Punkt innerhalb der Festung gilt als blockiert, wenn erecht (strikt) im Inneren eines der Rechtecke liegt (Punkte auf dem Rand der Rechtecke gelten nicht als im Inneren liegend).

Little S ist ein Wächter dieser Festung. Er steht an einem nicht blockierten Punkt $(x, y)$ innerhalb der Festung. Little S kann einen anderen Punkt $(x', y')$ innerhalb der Festung genau dann bewachen, wenn jeder Punkt auf der Strecke $(x, y) - (x', y')$ (einschließlich der beiden Endpunkte) nicht blockiert ist. Die Aufgabe besteht darin, den Flächeninhalt der Menge aller Punkte zu berechnen, die Little S bewachen kann, was der Fläche des Festungsgeländes entspricht, die Little S überblicken kann.

Eingabe

Dieses Problem enthält mehrere Testfälle. Die erste Zeile der Eingabe enthält eine Ganzzahl $T$ ($1 \le T \le 10^5$), die die Anzahl der Testfälle angibt.

Für jeden Testfall gilt:

• Die erste Zeile enthält zwei Ganzzahlen $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$), die den Radius der Festung und die Anzahl der Rechtecke darstellen.
• Die nächsten $n$ Zeilen enthalten jeweils vier Ganzzahlen $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$), die ein Rechteck beschreiben, wobei $(x_1, y_1)$ die Koordinaten der unteren linken Ecke und $(x_2, y_2)$ die Koordinaten der oberen rechten Ecke darstellt. Es wird garantiert, dass alle Rechtecke strikt innerhalb des Festungsgebiets liegen und den Rand des Gebiets nicht berühren.
• Die letzte Zeile enthält zwei Ganzzahlen $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$), die die Koordinaten von Little S darstellen. Es wird garantiert, dass der Punkt $(x, y)$ nicht blockiert ist.

Es wird garantiert, dass die Gesamtsumme von $n$ über alle Testfälle $10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit einer reellen Zahl aus, die den Flächeninhalt der Punktmenge darstellt, die Little S innerhalb der Festung bewachen kann.

Die Antwort gilt als korrekt, wenn der relative oder absolute Fehler im Vergleich zur Musterlösung kleiner als $10^{-6}$ ist. Mit anderen Worten: Wenn deine Ausgabe $a$ und die Musterlösung $b$ ist, gilt deine Ausgabe genau dann als korrekt, wenn $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$.

Beispiel

Eingabe

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

Ausgabe

5.598332050807308
513.142778328943998

Hinweis

Für den ersten Testfall sieht das zugehörige Bild wie folgt aus:

Für den zweiten Testfall sieht das zugehörige Bild wie folgt aus: