Planet Squanch

Time Limit: 2 Seconds    Memory Limit: 32768 KB

Forget Mars, scientists have discovered a new Earth-sized, possibly habitable, planet just 11 light years away. Known as Squanch, the newly discovered planet orbits a life-friendly red dwarf star that is an estimated seven billion years old.

After discovering Squanch, space agencies started competing to find places on the planet that support life. 

NASA and the Russian Space Agency, both have sent their own designed robots to investigate the planet and find an area of the surface with a better chance at hosting an atmosphere that could support life. These two robots have different algorithms to find the habitable area, so they could possibly report different areas as habitable. And of course, these two areas could share some areas of the surface. Since both robots are reliable, reported area by each of them would support life.

Since Squanch is big enough, we can consider the surface to be a giant plane instead of a curved surface, so the area that a robot reports, forms a polygon on a plane. Each robot will send signals to its own agency and report the x-y positions of vertices of the polygon they’ve found. The origin point (0, 0) for both robots is the same.

Help scientist to find the total area on Squanch that supports life.

Input

The first line of input contains a single integer T (1 ≤ T ≤ 64), which is the number of test cases.

For each test case, the first line contains two integers 3 ≤ n, m ≤ 50, the number of vertices of the two polygons. The next n lines each contain two real numbers (xi, yi) (distances are in kilometers), the coordinates of the vertices of the first polygon, followed by m lines with the same format for the vertices of the second polygon.

Output

For each test case, print the area in km2 that can support life, rounded up to 3 decimal places.

Sample Input

1
3 3
0 0
1 0
0 2
0 0
0 2
1 2

Sample Output

1.500
Submit

Source: 15th Iran Nationwide Internet Contest