У двовимірній відеогрі з фізичною моделлю два персонажі $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