Irregular Cakes (Small)

Mary the mathematician opened a bakery a few years ago. She is tired of baking the same rectangular and circular cakes, so for her next birthday she wants to bake an irregular cake, defined as the region between two polylines from $x = 0$ to $x = W$. The two polylines are called the lower boundary and the upper boundary.

A polyline is defined by a sequence of points $(P_0, P_1, \dots, P_n)$ listed from left to right. Joining consecutive points with line segments produces the polyline.

Today is Mary's birthday and she has baked an irregular cake bounded by a lower boundary with $L$ points and an upper boundary with $U$ points. After singing "Happy Birthday", she wants to make $G - 1$ vertical cuts that split the cake into $G$ slices of equal area, one for every guest. The irregular shape makes the cut positions hard to find. Compute where she has to cut.

The first line contains the number of test cases $T$. $T$ test cases follow.

The first line of each test case contains four integers separated by spaces: $W$ (the width of the cake), $L$ (the number of points on the lower boundary), $U$ (the number of points on the upper boundary) and $G$ (the number of guests).

The next $L$ lines describe the lower boundary. The $i$-th of those lines contains the coordinates $x_i$ and $y_i$ of the $i$-th point of the lower boundary. The next $U$ lines describe the upper boundary in the same format.

Limits

• $1 \le T \le 100$
• $1 \le W \le 1000$
• $2 \le L \le 100$
• $2 \le U \le 100$
• Every coordinate is an integer between $-1000$ and $1000$, inclusive.
• The leftmost point of each boundary has $x$ coordinate $0$.
• The rightmost point of each boundary has $x$ coordinate $W$.
• The points of one boundary are given in increasing order of $x$ coordinate and their $x$ coordinates are distinct.
• The lower boundary is strictly below the upper boundary for every $x$ between $0$ and $W$, inclusive. That is, at every $x$ position the $y$ coordinate of the lower boundary is smaller than the $y$ coordinate of the upper boundary.
• $2 \le G \le 3$

For each test case, print $G$ lines. The first line is Case #x:, where x is the test case number starting from 1. The next $G - 1$ lines contain the $x$ coordinates of the cuts, one per line, ordered from the leftmost cut to the rightmost cut.

The height of the cake is positive everywhere, so the area measured from the left edge increases strictly with $x$ and each cut position is unique.

Print each coordinate with exactly six digits after the decimal point, rounding the seventh digit half up. If the answer is $5$, print 5.000000. In every test file the exact answer is at least $10^{-7}$ away from a value whose rounding would change.