409421: GYM103535 I Smzzl with Safe Zone

A boy, whose ID is smzzl, is playing a game named Zig-Zag-Land(ZZL). This is a 2D battle royale game. When the game starts, you will spawn in a random place in the map, and your target is to move into the safe zone.

Given the border of the map and the border of the safe zone, he wants to know the shortest distance between the spawn point and the safe zone in the worst case.

It can be proved that the square of the answer is always rational. In order to check your answer precisely, you need to print the square of your answer modulo $$$10^9+7$$$. You may find the way to modulo a rational number in Problem F.

The input consists of multiple test cases.

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$) – the number of test cases.

For each test case:

In the first line, there is an integer $$$m$$$ ($$$3 \leq m \leq 10^5$$$), which is the number of vertexes of the safe zone.

In the next $$$m$$$ lines, each line contains two integers $$$x_i,y_i$$$ ($$$|x_i|,|y_i| \leq 10^7$$$), which is a vertex of the safe zone.

In the next line, there is an integer $$$n$$$ ($$$3 \leq n \leq 10^5$$$), which is the number of vertexes of the game map.

In the next $$$n$$$ lines, each line contains two integers $$$x_i,y_i$$$ ($$$|x_i|,|y_i| \leq 10^7$$$), which is a vertex of the game map.

It is guaranteed that:

• The safe zone is a subset of game map.
• The safe zone and the game map are both convex polygons.
• All vertexes are given in counter-clockwise order.
• The sum of $$$n$$$ over all test cases will not exceed $$$10^6$$$.
• The sum of $$$m$$$ over all test cases will not exceed $$$10^6$$$.

You may need to use faster input method.

For each test case, output the square of your answer modulo $$$10^9+7$$$.

1
4
0 0
1 0
1 1
0 1
4
-1 -1
2 -1
2 2
-1 2

2