في أرض بعيدة، توجد قلعة. إذا مثّلنا الاتجاهات باستخدام نظام الإحداثيات الديكارتية، فيمكن النظر إلى أراضي القلعة على أنها دائرة مركزها نقطة الأصل ونصف قطرها $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

ملاحظة

بالنسبة لحالة الاختبار الأولى، الصورة المقابلة هي كما يلي:

بالنسبة لحالة الاختبار الثانية، الصورة المقابلة هي كما يلي: