Cutting Cake

Today is the birthday of you and your twin sibling. To celebrate, you got a rectangular cake to share. The cake is decorated with $N$ triangular patches of icing (which may overlap). All the icing patches were made with the same triangular mold, so they have the same shape and orientation. Although you and your twin are very alike, your tastes in icing are very different. This difference is expressed by each of you having a different enjoyment value for each patch of icing. Specifically, your enjoyment for eating the entire $i$-th patch is $A_i$, and your twin's is $B_i$. If someone eats part of a patch, they get enjoyment proportional to the eaten area. For example, if you eat 2/3 of the area of the $i$-th patch, you get $\frac{2A_i}{3}$ enjoyment from it. Some flavors of icing may be disliked by you or your twin, so $A_i$ and/or $B_i$ can be negative.

You will cut the cake into two rectangular pieces with a single vertical cut (parallel to the Y-axis). After cutting, you eat the left piece and your twin eats the right piece. Your total enjoyment is the sum of the enjoyment you get from all icing to the left of the cut. Similarly, your twin's total enjoyment is the sum of the enjoyment they get from all icing to the right of the cut. To be as fair as possible, you want to choose the cut so that the absolute difference between your total enjoyment and your twin's total enjoyment is as small as possible. Given the $N$ triangular icing patches on a rectangular cake, what is the minimum possible absolute difference between your and your twin's total enjoyment that you can get with a single vertical cut?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing three positive integers $N$, $W$, and $H$: the number of icing patches on the cake, and the width and height of the top of the cake. The bottom-left corner of the cake is at $(0, 0)$ and the top-right corner is at $(W, H)$. Next comes a line describing the icing patch mold, with four integers $P$, $Q$, $R$, and $S$. The mold is a triangle with vertices at $(0, 0)$, $(P, Q)$, and $(R, S)$. Then $N$ lines follow. The $i$-th of these lines contains four integers $X_i$, $Y_i$, $A_i$, and $B_i$. The $i$-th patch is a triangle with vertices at $(X_i, Y_i)$, $(X_i + P, Y_i + Q)$, and $(X_i + R, Y_i + S)$. Eating all of it gives you $A_i$ enjoyment and your twin $B_i$.

For each test case, output one line containing Case #x: y/z, where $x$ is the test case number (starting from 1) and $y/z$ is the minimum absolute difference between your and your twin's total enjoyment that can be achieved with a single vertical cut, written as an irreducible fraction. $z$ must be positive and as small as possible.

In Sample 1, there is a single icing patch. The optimal cut is to the left of the patch. You eat no icing and get 0 enjoyment. Your twin eats the entire patch and gets 5 enjoyment from it. The absolute difference is $|0 - 5| = 5$.

In Sample 2, there are two icing patches. The optimal cut is at $X = 15099999.99$. The numerator and denominator of the answer can get very large.

In Sample 3, there are two icing patches. The optimal cut is at $X = 4$. You eat 75% of the first patch and get $-3$ enjoyment from it. Your twin eats 25% of the first patch and all of the second patch, getting $5 \cdot 0.25 + 5 = 6.25$ enjoyment. The absolute difference is $|-3 - 6.25| = 9.25 = \frac{37}{4}$.

Cutting at $X = 1$ gives you 0 enjoyment and your twin 10. Both values are larger than the ones at $X = 4$, but the difference is 10, which is greater than 9.25, so $X = 4$ is still better.

In Sample 4, there are three icing patches. The optimal cut is at $X \approx 521241077.6027$.