I et 2D-fysikkbasert videospill beveger to figurer $P$ og $Q$ seg over slagmarken. Hver figur er representert av et konvekst polygon som fungerer som dens kollisjonsboks. Når de to kollisjonsboksene overlapper, beregner spillet arealet av snittet deres som kollisjonsskaden.

På grunn av uforutsigbare vindstrømmer på arenaen kan imidlertid figur $Q$ bli forskjøvet med en vilkårlig translasjonsvektor $\mathbf{t} = (t_x, t_y)$, men den kan ikke rotere eller speilvendes. Du må beregne den forventede kollisjonsskaden når $Q$ plasseres uniformt og tilfeldig slik at den faktisk kolliderer med $P$, dvs. at snittet deres har et positivt areal.

Mer formelt, definer $f(\mathbf{t})$ som arealet av snittet mellom polygonet som representerer figur $P$ og polygonet som representerer figur $Q$ etter å ha blitt translatert langs $\mathbf{t}$. La $D \subseteq \mathbb{R}^2$ være mengden av alle translasjonsvektorer $\mathbf{t}$ der $f(\mathbf{t}) > 0$. Det kan vises at $D$ har et positivt areal, betegnet med $|D|$. Du må beregne $\frac{1}{|D|} \iint_D f(\mathbf{t})\,d\mathbf{t}$.

Inndata

Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 300$), som angir antallet testtilfeller. For hvert testtilfelle:

• Den første linjen inneholder to heltall $n$ og $m$ ($3 \le n, m \le 1\,000$), som angir antallet hjørner i de to konvekse polygonene.
• Deretter følger $n$ linjer, som hver inneholder to heltall $x$ og $y$ ($-10^4 \le x, y \le 10^4$), som gir hjørnekoordinatene $(x, y)$ til polygonet som representerer figur $P$.
• Deretter følger $m$ linjer, som hver inneholder to heltall $x$ og $y$ ($-10^4 \le x, y \le 10^4$), som gir hjørnekoordinatene $(x, y)$ til polygonet som representerer figur $Q$.
• Det er garantert at hjørnene til et konvekst polygon er gitt i rekkefølge mot klokken, og at ingen tre av dem ligger på samme linje.

Det er garantert at både summen av $n$ og summen av $m$ over alle testtilfeller ikke overstiger $1\,000$.

Utdata

For hvert testtilfelle skal du skrive ut en linje med et reelt tall som representerer den forventede kollisjonsskaden.

Svaret ditt godtas hvis den absolutte eller relative feilen ikke overstiger $10^{-6}$. Formelt sett, anta at utdataene dine er $a$ og juryens svar er $b$; utdataene dine godtas hvis og bare hvis $\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$.

Eksempler

Inndata 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