I ett 2D-fysikbaserat datorspel rör sig två karaktärer $P$ och $Q$ över slagfältet. Varje karaktär representeras av en konvex polygon som fungerar som dess kollisionsruta (collision box). När de två kollisionsrutorna överlappar varandra beräknar spelet arean av deras snitt som kollisionsskadan.

På grund av oförutsägbara vindströmmar på arenan kan karaktär $Q$ dock förflyttas med en godtycklig translationsvektor $\mathbf{t} = (t_x, t_y)$, men den kan inte rotera eller speglas. Du ska beräkna den förväntade kollisionsskadan när $Q$ placeras likformigt och slumpmässigt så att den faktiskt kolliderar med $P$, det vill säga så att deras snitt har en positiv area.

Mer formellt, definiera $f(\mathbf{t})$ som arean av snittet mellan polygonen som representerar karaktär $P$ och polygonen som representerar karaktär $Q$ efter att ha translaterats längs $\mathbf{t}$. Låt $D \subseteq \mathbb{R}^2$ vara mängden av alla translationsvektorer $\mathbf{t}$ för vilka $f(\mathbf{t}) > 0$. Det kan visas att $D$ har en positiv area, betecknad med $|D|$. Du ska beräkna $\frac{1}{|D|} \iint_D f(\mathbf{t})\,d\mathbf{t}$.

Indata

Den första raden i indata innehåller ett heltal $T$ ($1 \le T \le 300$), som anger antalet testfall. För varje testfall:

• Den första raden innehåller två heltal $n$ och $m$ ($3 \le n, m \le 1\,000$), som anger antalet hörn i de två konvexa polygonerna.
• Därefter följer $n$ rader som var och en innehåller två heltal $x$ och $y$ ($-10^4 \le x, y \le 10^4$), vilka anger hörnkoordinaterna $(x, y)$ för polygonen som representerar karaktär $P$.
• Därefter följer $m$ rader som var och en innehåller två heltal $x$ och $y$ ($-10^4 \le x, y \le 10^4$), vilka anger hörnkoordinaterna $(x, y)$ för polygonen som representerar karaktär $Q$.
• Det garanteras att hörnen i varje konvex polygon anges i moturs ordning och att inga tre av dem ligger på samma linje.

Det garanteras att såväl summan av $n$ som summan av $m$ över alla testfall inte överstiger $1\,000$.

Utdata

För varje testfall, skriv ut en rad som innehåller ett reellt tal som representerar den förväntade kollisionsskadan.

Ditt svar godkänns om dess absoluta eller relativa fel inte överstiger $10^{-6}$. Formellt sett, anta att din utdata är $a$ och juryns svar är $b$; din utdata godkänns om och endast om $\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$.

Exempel

Indata 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

Utdata 1

0.083333333333
0.125000000000