У далекій країні стоїть фортеця. Якщо зобразити місцевість у декартовій системі координат, територію фортеці можна розглядати як круг із центром у початку координат і радіусом $R$. Межа території фортеці оточена високими мурами, тому зсередини фортеці неможливо побачити те, що відбувається зовні.

Усередині фортеці є кілька будівель. Для зручності межі будівель подано у вигляді $n$ прямокутників, які можуть перетинатися, а їхні сторони паралельні осям координат. Точка всередині фортеці вважається заблокованою, якщо вона лежить строго всередині будь-якого з прямокутників (точки на межі прямокутників не вважаються такими, що лежать усередині).

Маленький S — охоронець цієї фортеці. Він стоїть у деякій незаблокованій точці $(x, y)$ всередині фортеці. Маленький S може охороняти іншу точку $(x', y')$ всередині фортеці тоді й лише тоді, коли кожна точка відрізка $(x, y) - (x', y')$ (включно з обома кінцями) не є заблокованою. Завдання полягає в тому, щоб обчислити площу множини точок, які може охороняти Маленький S, що відповідає площі території фортеці, яку Маленький 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$), що позначають координати Маленького S. Гарантується, що точка $(x, y)$ не є заблокованою.

Гарантується, що загальна сума $n$ за всіма наборами вхідних даних не перевищує $10^5$.

Вихідні дані

Для кожного набору вхідних даних виведіть в окремому рядку дійсне число, що позначає площу множини точок, які Маленький 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

Примітка

Для першого набору вхідних даних відповідне зображення наведено нижче:

Для другого набору вхідних даних відповідне зображення наведено нижче: