W odległej krainie znajduje się twierdza. Jeśli przedstawimy orientację za pomocą kartezjańskiego układu współrzędnych, terytorium twierdzy można traktować jako koło o środku w początku układu współrzędnych i promieniu $R$. Granica terytorium twierdzy jest otoczona wysokimi murami i z wnętrza twierdzy nie da się zobaczyć tego, co znajduje się na zewnątrz.

Wewnątrz twierdzy znajduje się kilka budynków. Dla wygody granice budynków są reprezentowane przez $n$ mogących na siebie nachodzić prostokątów, których boki są równoległe do osi układu współrzędnych. Punkt wewnątrz twierdzy uważa się za zablokowany, jeśli leży ściśle wewnątrz któregokolwiek z prostokątów (punkty na brzegu prostokątów nie są uznawane za leżące wewnątrz).

Little S jest strażnikiem tej twierdzy. Stoi on w pewnym niezablokowanym punkcie $(x, y)$ wewnątrz twierdzy. Little S może strzec innego punktu $(x', y')$ wewnątrz twierdzy wtedy i tylko wtedy, gdy każdy punkt na odcinku $(x, y) - (x', y')$ (włącznie z oboma końcami) jest niezablokowany. Zadaniem jest obliczenie pola zbioru punktów, których Little S może strzec, co odpowiada powierzchni terenu twierdzy, którą Little S może nadzorować.

Wejście

To zadanie zawiera wiele przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^5$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego:

• Pierwszy wiersz zawiera dwie liczby całkowite $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$), oznaczające promień twierdzy oraz liczbę prostokątów.
• Kolejne $n$ wierszy zawiera po cztery liczby całkowite $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$), opisujące prostokąt, gdzie $(x_1, y_1)$ oznacza współrzędne lewego dolnego rogu, a $(x_2, y_2)$ oznacza współrzędne prawego górnego rogu. Gwarantowane jest, że wszystkie prostokąty leżą ściśle wewnątrz terytorium twierdzy i nie dotykają granicy terytorium.
• Ostatni wiersz zawiera dwie liczby całkowite $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$), oznaczające współrzędne Little S. Gwarantowane jest, że punkt $(x, y)$ nie jest zablokowany.

Gwarantowane jest, że suma $n$ we wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w pojedynczym wierszu liczbę rzeczywistą oznaczającą pole zbioru punktów, których Little S może strzec wewnątrz twierdzy.

Odpowiedź zostanie uznana za poprawną, jeśli błąd względny lub bezwzględny względem odpowiedzi wzorcowej będzie mniejszy niż $10^{-6}$. Innymi słowy, jeśli Twoje wyjście to $a$, a odpowiedź wzorcowa to $b$, odpowiedź zostanie uznana za poprawną wtedy i tylko wtedy, gdy $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$.

Przykład

Wejście

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

Wyjście

5.598332050807308
513.142778328943998

Uwaga

Dla pierwszego przypadku testowego odpowiedni rysunek wygląda następująco:

Dla drugiego przypadku testowego odpowiedni rysunek wygląda następująco: