En un videojuego 2D basado en física, dos personajes $P$ y $Q$ se mueven por el campo de batalla. Cada personaje está representado por un polígono convexo que sirve como su caja de colisión. Cuando las dos cajas de colisión se superponen, el juego calcula el área de su intersección como el daño por colisión.

Sin embargo, debido a las corrientes de viento impredecibles en la arena, el personaje $Q$ puede desplazarse mediante un vector de traslación arbitrario $\mathbf{t} = (t_x, t_y)$, pero no puede rotar ni voltearse. Debes calcular el daño por colisión esperado cuando $Q$ se coloca de forma uniforme y aleatoria de modo que realmente colisione con $P$, es decir, que su intersección tenga un área positiva.

Más formalmente, define $f(\mathbf{t})$ como el área de la intersección entre el polígono que representa al personaje $P$ y el polígono que representa al personaje $Q$ tras ser trasladado a lo largo de $\mathbf{t}$. Sea $D \subseteq \mathbb{R}^2$ el conjunto de todos los vectores de traslación $\mathbf{t}$ para los cuales $f(\mathbf{t}) > 0$. Se puede demostrar que $D$ tiene un área positiva, denotada por $|D|$. Debes calcular $\frac{1}{|D|} \iint_D f(\mathbf{t})\,d\mathbf{t}$.

Entrada

La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 300$), que indica el número de casos de prueba. Para cada caso de prueba:

• La primera línea contiene dos enteros $n$ y $m$ ($3 \le n, m \le 1\,000$), que indican el número de vértices de los dos polígonos convexos, respectivamente.
• A continuación siguen $n$ líneas, cada una con dos enteros $x$ e $y$ ($-10^4 \le x, y \le 10^4$), que dan las coordenadas $(x, y)$ de los vértices del polígono que representa al personaje $P$.
• Luego siguen $m$ líneas, cada una con dos enteros $x$ e $y$ ($-10^4 \le x, y \le 10^4$), que dan las coordenadas $(x, y)$ de los vértices del polígono que representa al personaje $Q$.
• Se garantiza que los vértices de un polígono convexo se dan en sentido antihorario y que no hay tres de ellos que sean colineales.

Se garantiza que tanto la suma de $n$ como la suma de $m$ en todos los casos de prueba no superan $1\,000$.

Salida

Para cada caso de prueba, imprime una línea con un número real que represente el daño por colisión esperado.

Tu respuesta se considerará aceptable si su error absoluto o relativo no supera $10^{-6}$. Formalmente, supongamos que tu salida es $a$ y la respuesta del jurado es $b$; tu salida será aceptada si y solo si $\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$.

Ejemplos

Entrada 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

Salida 1

0.083333333333
0.125000000000