בארץ רחוקה ניצב מבצר. אם נייצג את המרחב באמצעות מערכת צירים קרטזית, ניתן לראות את שטח המבצר כעיגול שמרכזו בראשית הצירים ורדיוסו $R$. גבול שטח המבצר מוקף בחומות גבוהות, ואי אפשר לראות את החוץ מתוך המבצר.

בתוך המבצר ישנם מספר מבנים. לשם נוחות, גבולות המבנים מיוצגים על ידי $n$ מלבנים העשויים לחפוף זה לזה, שצלעותיהם מקבילות לצירי הקואורדינטות. נקודה בתוך המבצר נחשבת חסומה אם היא נמצאת ממש (באופן חזק) בתוך אחד המלבנים (נקודות על שפת המלבנים אינן נחשבות בפנים).

Little S הוא שומר במבצר זה. הוא עומד בנקודה לא חסומה כלשהי $(x, y)$ בתוך המבצר. Little S יכול לשמור על נקודה אחרת $(x', y')$ בתוך המבצר אם ורק אם כל נקודה על הקטע $(x, y) - (x', y')$ (כולל שתי נקודות הקצה) אינה חסומה. המשימה היא לחשב את שטח קבוצת הנקודות ש-Little S יכול לשמור עליהן, המייצג את שטח אדמת המבצר ש-Little S יכול להשגיח עליו.

קלט

בעיה זו מכילה מספר מקרי בדיקה. השורה הראשונה של הקלט מכילה מספר שלם $T$ ($1 \le T \le 10^5$), המציין את מספר מקרי הבדיקה.

עבור כל מקרה בדיקה:

• השורה הראשונה מכילה שני מספרים שלמים $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$), המייצגים את רדיוס המבצר ואת מספר המלבנים.
• $n$ השורות הבאות מכילות כל אחת ארבעה מספרים שלמים $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$), המתארים מלבן, כאשר $(x_1, y_1)$ מייצג את קואורדינטות הפינה השמאלית התחתונה ו-$(x_2, y_2)$ מייצג את קואורדינטות הפינה הימנית העליונה. מובטח שכל המלבנים נמצאים ממש בתוך שטח המבצר ואינם נוגעים בגבול השטח.
• השורה האחרונה מכילה שני מספרים שלמים $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$), המייצגים את הקואורדינטות של Little S. מובטח שהנקודה $(x, y)$ אינה חסומה.

מובטח שהסכום הכולל של $n$ על פני כל מקרי הבדיקה אינו עולה על $10^5$.

פלט

עבור כל מקרה בדיקה, הדפיסו שורה בודדת עם מספר ממשי המייצג את שטח קבוצת הנקודות ש-Little S יכול לשמור עליהן בתוך המבצר.

התשובה תיחשב נכונה אם השגיאה היחסית או המוחלטת בהשוואה לתשובה הרשמית קטנה מ-$10^{-6}$. במילים אחרות, אם הפלט שלכם הוא $a$ והתשובה הרשמית היא $b$, הפלט שלכם ייחשב נכון אם ורק אם $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$.

דוגמה

קלט

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

פלט

5.598332050807308
513.142778328943998

הערה

עבור מקרה הבדיקה הראשון, התמונה המתאימה היא כדלקמן:

עבור מקרה הבדיקה השני, התמונה המתאימה היא כדלקמן: