Dans une contrée lointaine se trouve une forteresse. Si nous représentons l'orientation à l'aide d'un système de coordonnées cartésiennes, le territoire de la forteresse peut être vu comme un cercle centré à l'origine et de rayon $R$. La frontière du territoire de la forteresse est entourée de hauts murs, et il est impossible de voir l'extérieur depuis l'intérieur de la forteresse.

À l'intérieur de la forteresse se trouvent quelques bâtiments. Par commodité, les limites des bâtiments sont représentées par $n$ rectangles pouvant se chevaucher et dont les côtés sont parallèles aux axes de coordonnées. Un point situé à l'intérieur de la forteresse est considéré comme bloqué s'il se trouve strictement à l'intérieur de l'un des rectangles (les points sur le bord des rectangles ne sont pas considérés comme étant à l'intérieur).

Little S est un garde de cette forteresse. Il se tient en un point non bloqué $(x, y)$ à l'intérieur de la forteresse. Little S peut garder un autre point $(x', y')$ à l'intérieur de la forteresse si et seulement si chaque point du segment $(x, y) - (x', y')$ (y compris les deux extrémités) n'est pas bloqué. La tâche consiste à calculer l'aire de l'ensemble des points que Little S peut garder, ce qui représente la superficie du terrain de la forteresse que Little S peut surveiller.

Entrée

Ce problème contient plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^5$), indiquant le nombre de cas de test.

Pour chaque cas de test :

• La première ligne contient deux entiers $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$), représentant le rayon de la forteresse et le nombre de rectangles.
• Les $n$ lignes suivantes contiennent chacune quatre entiers $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$), décrivant un rectangle, où $(x_1, y_1)$ représente les coordonnées du coin inférieur gauche et $(x_2, y_2)$ représente les coordonnées du coin supérieur droit. Il est garanti que tous les rectangles sont strictement à l'intérieur du territoire de la forteresse et ne touchent pas la frontière du territoire.
• La dernière ligne contient deux entiers $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$), représentant les coordonnées de Little S. Il est garanti que le point $(x, y)$ n'est pas bloqué.

Il est garanti que la somme totale de $n$ sur tous les cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un nombre réel représentant l'aire de l'ensemble des points que Little S peut garder au sein de la forteresse.

La réponse sera considérée comme correcte si l'erreur relative ou absolue par rapport à la réponse officielle est inférieure à $10^{-6}$. Autrement dit, si votre sortie est $a$ et la réponse officielle est $b$, votre sortie est considérée comme correcte si et seulement si $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$.

Exemple

Entrée

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

Sortie

5.598332050807308
513.142778328943998

Note

Pour le premier cas de test, l'image correspondante est la suivante :

Pour le second cas de test, l'image correspondante est la suivante :