케이크 자르기

오늘은 당신과 쌍둥이 형제자매의 생일이다. 이를 축하하려고 두 사람이 나눠 먹을 직사각형 케이크 한 개를 받았다. 케이크에는 삼각형 아이싱 패치 $N$ 개가 올려져 있다(겹칠 수 있다). 모든 아이싱 패치는 같은 삼각형 틀로 만들어져 모양과 방향이 같다. 당신과 쌍둥이는 많이 닮았지만 아이싱 취향은 크게 다르다. 이 차이는 아이싱 패치마다 둘의 즐거움 값이 다르다는 것으로 표현된다. 구체적으로, $i$ 번째 패치 전체를 먹을 때 당신의 즐거움은 $A_i$, 쌍둥이의 즐거움은 $B_i$이다. 패치의 일부만 먹으면 먹은 넓이에 비례하는 즐거움을 얻는다. 예를 들어 $i$ 번째 패치의 넓이 2/3를 먹으면 당신은 $\frac{2A_i}{3}$의 즐거움을 얻는다. 아이싱 맛에 따라 당신이나 쌍둥이가 싫어하는 경우도 있으므로 $A_i$나 $B_i$는 음수일 수 있다.

케이크를 Y축에 평행한 수직선 한 번으로 잘라 직사각형 두 조각으로 나눈다. 당신은 왼쪽 조각을, 쌍둥이는 오른쪽 조각을 먹는다. 당신의 총 즐거움은 자른 선 왼쪽에 있는 모든 아이싱에서 얻는 즐거움의 합이다. 쌍둥이의 총 즐거움도 같은 방식으로, 자른 선 오른쪽에 있는 아이싱에서 얻는 즐거움의 합이다. 공평하게 나누려고 두 사람의 총 즐거움 차이의 절댓값이 최대한 작아지도록 자르려고 한다. 직사각형 케이크 위의 삼각형 아이싱 패치 $N$ 개가 주어질 때, 수직선 한 번으로 자르면서 얻을 수 있는 두 사람 총 즐거움 차이 절댓값의 최솟값은 얼마인가?

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 양의 정수 $N$, $W$, $H$가 적힌 줄로 시작한다. $N$은 케이크 위 아이싱 패치의 개수이고, $W$와 $H$는 케이크 윗면의 너비와 높이이다. 케이크의 왼쪽 아래 모서리는 $(0, 0)$, 오른쪽 위 모서리는 $(W, H)$에 있다. 다음 줄에는 아이싱 틀을 나타내는 정수 $P$, $Q$, $R$, $S$가 주어진다. 틀은 꼭짓점이 $(0, 0)$, $(P, Q)$, $(R, S)$인 삼각형이다. 이어서 $N$개의 줄이 주어지며, $i$ 번째 줄에는 정수 $X_i$, $Y_i$, $A_i$, $B_i$가 주어진다. $i$ 번째 패치는 꼭짓점이 $(X_i, Y_i)$, $(X_i + P, Y_i + Q)$, $(X_i + R, Y_i + S)$인 삼각형이다. 이 패치 전체를 먹으면 당신은 $A_i$, 쌍둥이는 $B_i$의 즐거움을 얻는다.

각 테스트 케이스마다 Case #x: y/z 형식의 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y/z$는 수직선 한 번으로 자를 때 얻을 수 있는 두 사람 총 즐거움 차이 절댓값의 최솟값을 기약분수로 나타낸 것이다. $z$는 양수이며 가능한 값 중 가장 작아야 한다.

1번 예시에는 아이싱 패치가 하나뿐이다. 최적의 절단은 패치 왼쪽에서 자르는 것이다. 당신은 아이싱을 전혀 먹지 않아 즐거움이 0이다. 쌍둥이는 패치를 모두 먹어 5의 즐거움을 얻는다. 두 사람 즐거움 차이의 절댓값은 $|0 - 5| = 5$이다.

2번 예시에는 아이싱 패치가 두 개 있다. 최적의 절단은 $X = 15099999.99$ 지점이다. 답의 분자와 분모는 매우 커질 수 있다.

3번 예시에는 아이싱 패치가 두 개 있다. 최적의 절단은 $X = 4$ 지점이다. 당신은 첫 번째 패치의 75%를 먹어 $-3$의 즐거움을 얻는다. 쌍둥이는 첫 번째 패치의 25%와 두 번째 패치 전체를 먹어 $5 \cdot 0.25 + 5 = 6.25$의 즐거움을 얻는다. 두 사람 즐거움 차이의 절댓값은 $|-3 - 6.25| = 9.25 = \frac{37}{4}$이다.

$X = 1$에서 자르면 당신은 0, 쌍둥이는 10의 즐거움을 얻는다. 두 값 모두 $X = 4$에서 자를 때보다 크지만, 차이는 10으로 9.25보다 크므로 $X = 4$에서 자르는 것이 더 낫다.

4번 예시에는 아이싱 패치가 세 개 있다. 최적의 절단은 $X \approx 521241077.6027$ 지점이다.