Dans un jeu vidéo 2D basé sur la physique, deux personnages $P$ et $Q$ se déplacent sur le champ de bataille. Chaque personnage est représenté par un polygone convexe qui lui sert de boîte de collision. Lorsque les deux boîtes de collision se chevauchent, le jeu calcule l'aire de leur intersection comme étant les dégâts de collision.

Cependant, en raison de courants de vent imprévisibles dans l'arène, le personnage $Q$ peut être déplacé par un vecteur de translation arbitraire $\mathbf{t} = (t_x, t_y)$, mais il ne peut ni tourner ni se retourner. Vous devez calculer l'espérance des dégâts de collision lorsque $Q$ est placé de manière uniforme et aléatoire de telle sorte qu'il entre effectivement en collision avec $P$, c'est-à-dire que leur intersection ait une aire strictement positive.

Plus formellement, définissons $f(\mathbf{t})$ comme l'aire de l'intersection entre le polygone représentant le personnage $P$ et le polygone représentant le personnage $Q$ après translation selon $\mathbf{t}$. Soit $D \subseteq \mathbb{R}^2$ l'ensemble de tous les vecteurs de translation $\mathbf{t}$ pour lesquels $f(\mathbf{t}) > 0$. On peut montrer que $D$ a une aire strictement positive, notée $|D|$. Vous devez calculer $\frac{1}{|D|} \iint_D f(\mathbf{t})\,d\mathbf{t}$.

Entrée

La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 300$), désignant le nombre de cas de test. Pour chaque cas de test :

• La première ligne contient deux entiers $n$ et $m$ ($3 \le n, m \le 1\,000$), désignant respectivement les nombres de sommets des deux polygones convexes.
• Suivent ensuite $n$ lignes, contenant chacune deux entiers $x$ et $y$ ($-10^4 \le x, y \le 10^4$), donnant les coordonnées $(x, y)$ des sommets du polygone représentant le personnage $P$.
• Suivent ensuite $m$ lignes, contenant chacune deux entiers $x$ et $y$ ($-10^4 \le x, y \le 10^4$), donnant les coordonnées $(x, y)$ des sommets du polygone représentant le personnage $Q$.
• Il est garanti que les sommets d'un polygone convexe sont donnés dans le sens inverse des aiguilles d'une montre et qu'aucun triplet de sommets n'est aligné.

Il est garanti que la somme des $n$ et la somme des $m$ sur l'ensemble des cas de test ne dépassent pas $1\,000$.

Sortie

Pour chaque cas de test, affichez une ligne contenant un nombre réel représentant l'espérance des dégâts de collision.

Votre réponse est acceptée si son erreur absolue ou relative ne dépasse pas $10^{-6}$. Formellement, en supposant que votre sortie soit $a$ et que la réponse du jury soit $b$, votre sortie est acceptée si et seulement si $\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$.

Exemples

Entrée 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

Sortie 1

0.083333333333
0.125000000000