케이크 자르기

오늘은 당신과 쌍둥이 형제자매의 생일이다. 생일을 축하하기 위해 함께 나눠 먹을 직사각형 케이크를 준비했다. 케이크는 서로 겹칠 수도 있는 삼각형 모양의 아이싱 조각 $\mathbf{N}$개로 장식되어 있다. 모든 아이싱 조각은 동일한 삼각형 틀로 만들었으므로 모양과 방향이 같다. 당신과 쌍둥이는 매우 닮았지만 아이싱에 대한 취향은 크게 다르다. 이러한 차이는 각 아이싱 조각에 대해 두 사람이 서로 다른 만족도 값을 갖는 것으로 나타낸다. 구체적으로, 당신이 $i$⁠-⁠번째 아이싱 조각 전체를 먹을 때 얻는 만족도는 $\mathbf{A_i}$이고, 쌍둥이가 얻는 만족도는 $\mathbf{B_i}$이다. 누군가 아이싱 조각의 일부를 먹으면 먹은 넓이에 비례하는 만족도를 얻는다. 예를 들어 당신이 $i$⁠-⁠번째 아이싱 조각 넓이의 $\frac{2}{3}$을 먹으면 그 조각에서 $\frac{2\mathbf{A_i}}{3}$의 만족도를 얻는다. 당신이나 쌍둥이가 좋아하지 않는 아이싱 맛도 있을 수 있으므로, $\mathbf{A_i}$ 및/또는 $\mathbf{B_i}$의 값은 음수일 수 있음에 유의하라.

Y축과 평행한 하나의 수직 절단선을 내어 케이크를 직사각형 조각 두 개로 자른다. 케이크를 자른 뒤 당신은 왼쪽 조각을 먹고 쌍둥이는 오른쪽 조각을 먹는다. 당신의 총 만족도는 절단선 왼쪽에 있는 모든 아이싱에서 얻는 만족도의 합이다. 마찬가지로 쌍둥이의 만족도는 절단선 오른쪽에 있는 모든 아이싱에서 얻는 만족도의 합이다.

최대한 공평하게 나누기 위해, 당신의 총 만족도와 쌍둥이의 총 만족도 차이의 절댓값이 가능한 한 작아지도록 케이크를 자르려고 한다. 직사각형 케이크 위의 삼각형 아이싱 조각 $\mathbf{N}$개가 주어질 때, 당신과 쌍둥이의 총 만족도 차이의 절댓값으로 가능한 최솟값은 얼마인가?

제한

시간 제한: 45초. 메모리 제한: 1 GB.

테스트 세트 1 (Visible Verdict)

$1 \le \mathbf{T} \le 100$. $1 \le \mathbf{N} \le 100$. $3 \le \mathbf{W} \le 10^9$. $3 \le \mathbf{H} \le 10^9$. 모든 $i$에 대해 $-10^9 \le \mathbf{A_i} \le 10^9$. 모든 $i$에 대해 $-10^9 \le \mathbf{B_i} \le 10^9$. $0 \le \mathbf{P} \le 10^9$. $-10^9 \le \mathbf{Q} \le 10^9$. $0 \le \mathbf{R} \le 10^9$. $-10^9 \le \mathbf{S} \le 10^9$. 틀의 세 꼭짓점 $(0, 0)$, $(\mathbf{P}, \mathbf{Q})$, $(\mathbf{R}, \mathbf{S})$은 한 직선 위에 있지 않다. 각 삼각형 아이싱 조각의 세 꼭짓점은 케이크의 경계보다 엄격히 안쪽에 있다. 형식적으로는 다음과 같다. 모든 $i$에 대해 $1 \le \mathbf{X_i} \le \mathbf{W} - \max(\mathbf{P}, \mathbf{R}) - 1$, 그리고 모든 $i$에 대해 $\max(0, -\mathbf{Q}, -\mathbf{S}) + 1 \le \mathbf{Y_i} \le \mathbf{H} - \max(0, \mathbf{Q}, \mathbf{S}) - 1$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 케이크 위 아이싱 조각의 수와 케이크 윗면의 너비 및 높이를 각각 나타내는 세 양의 정수 $\mathbf{N}$, $\mathbf{W}$, $\mathbf{H}$이 포함된 줄로 시작한다. 케이크의 왼쪽 아래 모서리는 $(0, 0)$에 있고 오른쪽 위 모서리는 $(\mathbf{W}, \mathbf{H})$에 있다. 그다음 아이싱 조각의 틀을 설명하는 줄이 주어진다. 이 줄에는 네 정수 $\mathbf{P}$, $\mathbf{Q}$, $\mathbf{R}$, $\mathbf{S}$이 주어진다. 아이싱 조각의 틀은 꼭짓점이 $(0, 0)$, $(\mathbf{P}, \mathbf{Q})$, $(\mathbf{R}, \mathbf{S})$인 삼각형이다. 이어서 $\mathbf{N}$개의 줄이 주어진다. 이 줄들 중 $i$⁠-⁠번째 줄에는 네 정수 $\mathbf{X_i}$, $\mathbf{Y_i}$, $\mathbf{A_i}$, $\mathbf{B_i}$이 주어진다. $i$⁠-⁠번째 조각은 꼭짓점이 $(\mathbf{X_i}, \mathbf{Y_i})$, $(\mathbf{X_i} + \mathbf{P}, \mathbf{Y_i} + \mathbf{Q})$, $(\mathbf{X_i} + \mathbf{R}, \mathbf{Y_i} + \mathbf{S})$인 삼각형이다. 이를 먹으면 당신은 $\mathbf{A_i}$의 만족도를 얻고 쌍둥이는 $\mathbf{B_i}$의 만족도를 얻는다.

각 테스트 케이스마다 Case #$x$: $y$/$z$을 한 줄에 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $\frac{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 \gt 9.25$이므로 그럼에도 $X = 4$에서 자르는 편이 더 낫다.

샘플 케이스 #4에는 아이싱 조각이 세 개 있다. 최적의 절단선은 $X \approx 521241077.6027$에 있다.