В далёкой стране стоит крепость. Если представить местность в декартовой системе координат, территорию крепости можно рассматривать как круг с центром в начале координат и радиусом $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

Примечание

Для первого набора входных данных соответствующий рисунок приведён ниже:

Для второго набора входных данных соответствующий рисунок приведён ниже: