В двумерной видеоигре, основанной на физике, два персонажа $P$ и $Q$ перемещаются по полю боя. Каждый персонаж представлен выпуклым многоугольником, который служит его хитбоксом (областью столкновения). Когда два хитбокса перекрываются, игра вычисляет площадь их пересечения в качестве урона от столкновения.

Однако из-за непредсказуемых потоков ветра на арене персонаж $Q$ может смещаться на произвольный вектор параллельного переноса $\mathbf{t} = (t_x, t_y)$, но не может поворачиваться или отражаться. Вам необходимо вычислить математическое ожидание урона от столкновения, когда $Q$ размещается равномерно и случайно таким образом, что он действительно сталкивается с $P$, то есть их пересечение имеет положительную площадь.

Более формально, определим $f(\mathbf{t})$ как площадь пересечения многоугольника, представляющего персонажа $P$, и многоугольника, представляющего персонажа $Q$ после параллельного переноса на вектор $\mathbf{t}$. Пусть $D \subseteq \mathbb{R}^2$ — множество всех векторов переноса $\mathbf{t}$, для которых $f(\mathbf{t}) > 0$. Можно показать, что $D$ имеет положительную площадь, обозначаемую $|D|$. Вам нужно вычислить $\frac{1}{|D|} \iint_D f(\mathbf{t})\,d\mathbf{t}$.

Входные данные

Первая строка входных данных содержит целое число $T$ ($1 \le T \le 300$) — количество наборов входных данных. Для каждого набора входных данных:

• Первая строка содержит два целых числа $n$ и $m$ ($3 \le n, m \le 1\,000$), обозначающих количество вершин двух выпуклых многоугольников соответственно.
• Далее следуют $n$ строк, каждая из которых содержит два целых числа $x$ и $y$ ($-10^4 \le x, y \le 10^4$), задающих координаты вершин $(x, y)$ многоугольника, представляющего персонажа $P$.
• Затем следуют $m$ строк, каждая из которых содержит два целых числа $x$ и $y$ ($-10^4 \le x, y \le 10^4$), задающих координаты вершин $(x, y)$ многоугольника, представляющего персонажа $Q$.
• Гарантируется, что вершины выпуклого многоугольника заданы в порядке обхода против часовой стрелки и никакие три из них не лежат на одной прямой.

Гарантируется, что как сумма $n$, так и сумма $m$ по всем наборам входных данных не превышают $1\,000$.

Выходные данные

Для каждого набора входных данных выведите строку, содержащую вещественное число — математическое ожидание урона от столкновения.

Ваш ответ будет засчитан, если его абсолютная или относительная погрешность не превышает $10^{-6}$. Формально говоря, если ваш вывод равен $a$, а ответ жюри равен $b$, ваш вывод принимается тогда и только тогда, когда $\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$.

Примеры

Входные данные 1

2
3 3
0 0
1 0
0 1
0 0
1 0
0 1
3 3
0 0
1 0
0 1
0 1
1 0
1 1

Выходные данные 1

0.083333333333
0.125000000000