Carving Pumpkins (part 2)

Note: This problem statement is identical to Carving Pumpkins (part 1), but requires convex quadrilateral eye and mouth shapes.

Now that we've bought some pumpkins, it's time to carve them into Jack-o'-lanterns.

A pumpkin can be considered an ellipse:

pumpkin-ellipse

Let's place the pumpkin on a coordinate axis, with its center exactly in $(0, 0)$ . Note that a point $(x, y)$ is strictly inside an ellipse with width $2 \cdot a$ and height $2 \cdot b$ if:

\frac{x ^{2}}{a ^{2}} + \frac{y ^{2}}{b ^{2}} < 1.

(If this formula seems off-putting, make sure to check out the pumpkin carving simulator!)

We want to carve a pair of eyes and a mouth into our pumpkin, according to the following rules:

The area of each eye must be exactly $E$ .
The area of the mouth must be exactly $M$ .
The eyes and the mouth must be convex quadrilaterals.
The vertices of each shape must be in integer coordinates.
The left eye, the right eye, and the mouth cannot touch or intersect each other, including sharing a vertex.
The eyes and the mouth cannot touch or go beyond the pumpkin shape (the ellipse).
The mouth must reside strictly below the x-axis.
Both eyes must reside strictly above the x-axis.
The left eye must reside strictly to the left of y-axis.
The right eye must reside strictly to the right of y-axis.

Given the width $W$ and height $H$ of the pumpkin, find a carving that satisfies the above constraints.

Input

The first line contains an integer $T$ — the number of test cases.

Each test case contains 4 integers $W$ , $H$ , $E$ , $M$ .

Constraints

$10 \leq H, W \leq 100$
$1 \leq E, M \leq 2000$
The input data will be chosen in such a way that at least one valid carving exists.

Output

For each test case, print Case #i:, followed by 3 lines.

Each line must contain 8 integers specifying the coordinates of the four vertices of a convex quadrilateral, listed in either clockwise or counterclockwise order: $(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3}), (x_{4}, y_{4})$ .

The first line specifies the left eye, the second line specifies the right eye, and the third line specifies the mouth.

Any carving that satisfies the rules will be accepted.

Examples

Input

2
33 24 8 56
33 24 10 10

Output

Case #1:
-6 4 -2 3 -2 2 -6 1
6 4 2 3 2 2 6 1
-8 -6 8 -6 6 -2 -6 -2
Case #2:
-12 4 -7 3 -4 2 -9 1
6 8 2 5 2 4 6 4
-4 -3 1 -6 2 -4 -3 -2

Explanation

Case 1. We have a pumpkin with height 24 and width 33, and need to carve out eyes with area 8 and mouth with area 56. The sample output makes them perfectly symmetric and mean-looking (as a good Jack o'lantern should be).

sample1

Case 2. We have a pumpkin with height 24 and width 33, and need to carve out eyes with area 10 and mouth with area 10. The sample output specifies a rather terrible carving, but it fits our rules regardless.

sample1

Feel free to try different carvings with the following simulator.