In una terra lontana c'è una fortezza. Se rappresentiamo l'orientamento usando un sistema di coordinate cartesiane, il territorio della fortezza può essere visto come un cerchio centrato nell'origine con raggio $R$. Il confine del territorio della fortezza è circondato da alte mura ed è impossibile vedere l'esterno dall'interno della fortezza.

All'interno della fortezza ci sono alcuni edifici. Per comodità, i confini degli edifici sono rappresentati da $n$ rettangoli, eventualmente sovrapposti, i cui lati sono paralleli agli assi coordinati. Un punto all'interno della fortezza è considerato bloccato se giace strettamente all'interno di uno qualsiasi dei rettangoli (i punti sul bordo dei rettangoli non sono considerati all'interno).

Little S è una guardia di questa fortezza. Si trova in un punto non bloccato $(x, y)$ all'interno della fortezza. Little S può sorvegliare un altro punto $(x', y')$ all'interno della fortezza se e solo se ogni punto sul segmento $(x, y) - (x', y')$ (inclusi i due estremi) non è bloccato. Il compito consiste nel calcolare l'area dell'insieme dei punti che Little S può sorvegliare, che rappresenta l'area del terreno della fortezza che Little S può controllare.

Input

Questo problema contiene più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^5$), che indica il numero di casi di test.

Per ciascun caso di test:

• La prima riga contiene due interi $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$), che rappresentano il raggio della fortezza e il numero di rettangoli.
• Le successive $n$ righe contengono ciascuna quattro interi $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$), che descrivono un rettangolo, dove $(x_1, y_1)$ rappresenta le coordinate dell'angolo inferiore sinistro e $(x_2, y_2)$ rappresenta le coordinate dell'angolo superiore destro. È garantito che tutti i rettangoli si trovino strettamente all'interno del territorio della fortezza e non tocchino il confine del territorio.
• L'ultima riga contiene due interi $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$), che rappresentano le coordinate di Little S. È garantito che il punto $(x, y)$ non sia bloccato.

È garantito che la somma totale di $n$ su tutti i casi di test non superi $10^5$.

Output

Per ciascun caso di test, stampa una singola riga con un numero reale che rappresenta l'area dell'insieme di punti che Little S può sorvegliare all'interno della fortezza.

La risposta sarà considerata corretta se l'errore relativo o assoluto rispetto alla risposta corretta è inferiore a $10^{-6}$. In altre parole, se il tuo output è $a$ e la risposta corretta è $b$, il tuo output è considerato corretto se e solo se $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$.

Esempio

Input

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

Output

5.598332050807308
513.142778328943998

Note

Per il primo caso di test, l'immagine corrispondente è la seguente:

Per il secondo caso di test, l'immagine corrispondente è la seguente: