Irregular Cakes (Large Input)

Mary the mathematician opened a bakery a few years ago. She has grown tired of baking the same rectangular and circular cakes all this time, so for her next birthday she wants to bake an irregular cake, which is the region between two polylines that run from $x=0$ to $x=W$. The lower polyline is the lower boundary and the upper polyline is the upper boundary.

A polyline is defined by a sequence of points $(P_0, P_1, \ldots, P_n)$ listed from left to right. Joining each pair of neighboring points with a line segment produces the polyline.

Today is Mary's birthday. She has baked an irregular cake bounded by a lower boundary with $L$ points and an upper boundary with $U$ points. After the birthday song she wants to make $G-1$ vertical cuts that split the cake into $G$ slices of equal area, so every guest gets one slice. The irregular shape makes the cut positions hard to work out. Find where Mary 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 $W$, $L$, $U$ and $G$ separated by spaces. $W$ is the width of the cake, $L$ is the number of points on the lower boundary, $U$ is the number of points on the upper boundary, and $G$ is the number of guests at the party.

The next $L$ lines give the lower boundary. The $i$-th of them contains the coordinates $x_i$ and $y_i$ of the $i$-th point on the lower boundary. The next $U$ lines give 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$
• $2 \le G \le 101$
• Every coordinate is an integer between $-1000$ and $1000$, inclusive.
• On both boundaries the leftmost point has $x$-coordinate $0$ and the rightmost point has $x$-coordinate $W$.
• Points on the same boundary are given in increasing order of $x$-coordinate, and their $x$-coordinates are distinct.
• For every $x$ with $0 \le x \le W$, the $y$-coordinate of the lower boundary is smaller than the $y$-coordinate of the upper boundary.

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 on the whole interval $0 \le x \le W$, so the area accumulated from the left increases strictly with $x$. Each cut position is therefore unique.

Round every coordinate to six digits after the decimal point, rounding a half up, and print all six digits. If the exact value is $5$, print 5.000000.