Connected Gheeves#5043

Connected Gheeves

1 second

64 megabytes

Hard

Gheeves (plural of gheef) are objects similar to funnels. We define a gheef as a two-dimensional object specified by a sequence of points $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n with the following properties:

$3 \leq n \leq 1000$ 3 \leq n \leq 1000.
If point $p_{i}$ p_i has coordinates $(x_{i}, y_{i})$ (x_i, y_i), then there exists an index $c$ with $1 < c < n$ 1 < c < n such that $y_{1} > y_{2} > \dots > y_{c}$ y_1 > y_2 > \ldots > y_c and $y_{c} < y_{c + 1} < y_{c + 2} < \dots < y_{n}$ y_c < y_{c+1} < y_{c+2} < \ldots < y_n. The point $p_{c}$ p_c is called the cusp of the gheef.
For all $1 \leq i < c$ 1 \leq i < c, $x_{i} < x_{c}$ x_i < x_c; for all $c < i \leq n$ c < i \leq n, $x_{i} > x_{c}$ x_i > x_c.
For $1 < i < c$ 1 < i < c, the angle by which $p_{i - 1}$ p_{i-1} has to be rotated around $p_{i}$ p_i in the clockwise direction to become collinear with $p_{i}$ p_i and $p_{i + 1}$ p_{i+1} is greater than $180$ degrees. Likewise, for $c < i < n$ c < i < n, the needed angle for $p_{i - 1}$ p_{i-1} to become collinear with $p_{i}$ p_i and $p_{i + 1}$ p_{i+1} (by clockwise rotation around $p_{i}$ p_i) is also greater than $180$ degrees.
The line segments connecting every two consecutive points $p_{i}$ p_i and $p_{i + 1}$ p_{i+1} intersect only at their endpoints.

For example, the following figure shows a gheef with six points and $c = 4$ c = 4:

We call the sequence of segments $p_{1} p_{2}, p_{2} p_{3}, \dots, p_{n - 1} p_{n}$ p_1p_2, p_2p_3, \ldots, p_{n-1}p_n the body of the gheef. In this problem, you are given two gheeves $P = (p_{1}, p_{2}, \dots, p_{n})$ P = (p_1, p_2, \ldots, p_n) and $Q = (q_{1}, q_{2}, \dots, q_{m})$ Q = (q_1, q_2, \ldots, q_m), such that all $x$ -coordinates of $p_{i}$ p_i are negative integers, and all $x$ -coordinates of $q_{i}$ q_i are positive integers.

Assume the cusps of the two gheeves are connected by a narrow pipe. Water is poured into the gheeves; as water is poured, the gheeves fill upwards according to basic physical laws (the water level in both gheeves remains the same). When the water level in gheef $P$ reaches $min (y_{1}, y_{n})$ \min(y_1, y_n), water will begin to spill out of $P$ (the same holds for $Q$ ).

You must determine the final water level in the gheeves after a specified amount of water has been poured. Since the problem is considered in two dimensions, the amount of water is measured by the area it fills. Assume the volume of the connecting pipe is zero.

Input

The first line contains the number of test cases $t$ . Each test case consists of three lines. The first of these three lines contains an integer $a$ ( $1 \leq a \leq 100000$ 1 \leq a \leq 100000), the amount of water poured into the two gheeves. The next two lines describe $P$ and $Q$ . Each gheef is specified as $k$ $x_{1} y_{1} x_{2} y_{2} \dots x_{k} y_{k}$ x_1 y_1 x_2 y_2 \ldots x_k y_k, where $k$ is the number of points in the gheef ( $n$ for $P$ and $m$ for $Q$ ), and the $x_{i}, y_{i}$ x_i, y_i pairs are the coordinates of the points of the gheef in sequence.

Output

Print $t$ lines, one for each test case. Each line should contain a single number $L$ —the final water level, as a real number in units of the $y$ coordinate, rounded to three decimal places.

Examples

Example 1