In un videogioco 2D basato sulla fisica, due personaggi $P$ e $Q$ si muovono sul campo di battaglia. Ogni personaggio è rappresentato da un poligono convesso che funge da suo riquadro di collisione (collision box). Quando i due riquadri di collisione si sovrappongono, il gioco calcola l'area della loro intersezione come danno da collisione.

Tuttavia, a causa di imprevedibili correnti di vento nell'arena, il personaggio $Q$ può essere spostato di un vettore di traslazione arbitrario $\mathbf{t} = (t_x, t_y)$, ma non può ruotare né ribaltarsi. Devi calcolare il danno da collisione atteso quando $Q$ viene posizionato in modo uniforme e casuale tale da collidere effettivamente con $P$, ossia in modo che la loro intersezione abbia un'area positiva.

Più formalmente, definiamo $f(\mathbf{t})$ come l'area dell'intersezione tra il poligono che rappresenta il personaggio $P$ e il poligono che rappresenta il personaggio $Q$ dopo essere stato traslato lungo $\mathbf{t}$. Sia $D \subseteq \mathbb{R}^2$ l'insieme di tutti i vettori di traslazione $\mathbf{t}$ per i quali $f(\mathbf{t}) > 0$. Si può dimostrare che $D$ ha un'area positiva, indicata con $|D|$. Devi calcolare $\frac{1}{|D|} \iint_D f(\mathbf{t})\,d\mathbf{t}$.

Input

La prima riga dell'input contiene un intero $T$ ($1 \le T \le 300$), che indica il numero di casi di test. Per ciascun caso di test:

• La prima riga contiene due interi $n$ e $m$ ($3 \le n, m \le 1\,000$), che indicano rispettivamente il numero di vertici dei due poligoni convessi.
• Seguono poi $n$ righe, ciascuna contenente due interi $x$ e $y$ ($-10^4 \le x, y \le 10^4$), che forniscono le coordinate $(x, y)$ dei vertici del poligono che rappresenta il personaggio $P$.
• Seguono poi $m$ righe, ciascuna contenente due interi $x$ e $y$ ($-10^4 \le x, y \le 10^4$), che forniscono le coordinate $(x, y)$ dei vertici del poligono che rappresenta il personaggio $Q$.
• È garantito che i vertici di ciascun poligono convesso siano forniti in senso antiorario e che non vi siano tre vertici collineari.

È garantito che sia la somma di $n$ sia la somma di $m$ su tutti i casi di test non superino $1\,000$.

Output

Per ciascun caso di test, stampa una riga contenente un numero reale che rappresenta il danno da collisione atteso.

La tua risposta è considerata accettabile se il suo errore assoluto o relativo non supera $10^{-6}$. Formalmente, supponendo che il tuo output sia $a$ e la risposta della giuria sia $b$, il tuo output è accettato se e solo se $\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$.

Esempi

Input 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

Output 1

0.083333333333
0.125000000000