In einem 2D-physikbasierten Videospiel bewegen sich zwei Charaktere $P$ und $Q$ über das Schlachtfeld. Jeder Charakter wird durch ein konvexes Polygon dargestellt, das als seine Kollisionsbox dient. Wenn sich die beiden Kollisionsboxen überlappen, berechnet das Spiel den Flächeninhalt ihrer Schnittmenge als Kollisionsschaden.

Aufgrund unvorhersehbarer Windströmungen in der Arena kann Charakter $Q$ jedoch um einen beliebigen Verschiebungsvektor $\mathbf{t} = (t_x, t_y)$ verschoben werden, sich aber weder drehen noch spiegeln. Sie müssen den erwarteten Kollisionsschaden berechnen, wenn $Q$ gleichverteilt und zufällig so platziert wird, dass er tatsächlich mit $P$ kollidiert, d. h. ihre Schnittmenge einen positiven Flächeninhalt hat.

Formaler ausgedrückt: Definieren Sie $f(\mathbf{t})$ als den Flächeninhalt der Schnittmenge zwischen dem Polygon, das Charakter $P$ darstellt, und dem Polygon, das Charakter $Q$ nach der Verschiebung entlang $\mathbf{t}$ darstellt. Sei $D \subseteq \mathbb{R}^2$ die Menge aller Verschiebungsvektoren $\mathbf{t}$, für die $f(\mathbf{t}) > 0$ gilt. Es lässt sich zeigen, dass $D$ einen positiven Flächeninhalt besitzt, der mit $|D|$ bezeichnet wird. Sie müssen $\frac{1}{|D|} \iint_D f(\mathbf{t})\,d\mathbf{t}$ berechnen.

Eingabe

Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 300$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:

• Die erste Zeile enthält zwei ganze Zahlen $n$ und $m$ ($3 \le n, m \le 1\,000$), die jeweils die Anzahl der Eckpunkte der beiden konvexen Polygone angeben.
• Darauf folgen $n$ Zeilen mit jeweils zwei ganzen Zahlen $x$ und $y$ ($-10^4 \le x, y \le 10^4$), welche die Eckpunktkoordinaten $(x, y)$ des Polygons angeben, das Charakter $P$ darstellt.
• Darauf folgen $m$ Zeilen mit jeweils zwei ganzen Zahlen $x$ und $y$ ($-10^4 \le x, y \le 10^4$), welche die Eckpunktkoordinaten $(x, y)$ des Polygons angeben, das Charakter $Q$ darstellt.
• Es wird garantiert, dass die Eckpunkte eines konvexen Polygons gegen den Uhrzeigersinn angegeben sind und keine drei davon kollinear sind.

Es wird garantiert, dass sowohl die Summe von $n$ als auch die Summe von $m$ über alle Testfälle $1\,000$ nicht überschreitet.

Ausgabe

Geben Sie für jeden Testfall eine Zeile mit einer reellen Zahl aus, die den erwarteten Kollisionsschaden darstellt.

Ihre Antwort wird akzeptiert, wenn ihr absoluter oder relativer Fehler $10^{-6}$ nicht überschreitet. Formal ausgedrückt: Angenommen, Ihre Ausgabe ist $a$ und die Antwort der Jury ist $b$, dann wird Ihre Ausgabe genau dann akzeptiert, wenn $\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$ gilt.

Beispiele

Eingabe 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

Ausgabe 1

0.083333333333
0.125000000000