(거의) 공정한 케이크 자르기

공정한 케이크 자르기 방법은 잘 알려져 있습니다. 한 사람이 케이크를 두 조각으로 자르고, 다른 사람이 먹을 조각을 고릅니다. 두 참가자 모두 작은 조각을 받았다고 주장할 수 없으므로 이 방법은 공정하다고 여겨집니다.

그러나 앨리스의 집에서는 앨리스가 규칙을 정하며, 그 규칙은 전혀 공정하지 않습니다. 앨리스는 남동생 밥에게 한 번이 아니라 $n$번 자르라고 시킵니다. 자를 때마다 앨리스는 한쪽을 골라 그쪽의 케이크를 모두 먹습니다. 앨리스가 모든 자르기를 마치면 남은 케이크는 밥이 먹습니다.

케이크는 데카르트 평면 위에 있는 한 변의 길이가 $M$인 정사각형이며, 마주 보는 꼭짓점이 $(0, 0)$과 $(M, M)$에 있습니다. (실제로는 직육면체이지만, 모든 자르는 면은 표면에 수직이라고 가정합니다.) 밥이 $n$번 자르기를 마쳤고, 이제 앨리스가 선택할 차례입니다. 앨리스가 현명하게 고른다면 케이크를 얼마나 먹을 수 있는지 구하세요.

첫 줄에 테스트 케이스의 개수 $z$ ($1 \leq z \leq 500$)가 주어집니다. 이어서 각 테스트 케이스의 설명이 나옵니다.

각 테스트 케이스의 첫 줄에는 정수 두 개 $n$ ($1 \leq n \leq 4\,000$)과 $M$ ($1 \leq M \leq 1000$)이 주어집니다. 각각 자르기의 횟수와 케이크의 한 변의 길이입니다. 케이크는 마주 보는 꼭짓점이 $(0, 0)$과 $(M, M)$에 있는 정사각형입니다.

이어서 $n$개의 줄이 주어집니다. $i$번째 줄에는 정수 세 개 $A_i$, $B_i$, $C_i$ ($-1000 \leq A_i, B_i \leq 1000$, $-10^6 \leq C_i \leq 10^6$, $A_i^2 + B_i^2 > 0$)가 주어지며, 이는 $i$번째 자르기의 직선 방정식 $A_i x + B_i y + C_i = 0$을 정의합니다.

더 정확히 말하면, 앨리스는 $n$개의 직선 방정식을 받습니다. 각 방정식에서 $=$를 $\leq$ 또는 $\geq$로 바꿔 반평면을 얻습니다. 앨리스가 먹을 수 있는 영역은 케이크와 이 $n$개의 반평면을 모두 만족하는 영역의 교집합입니다.

각 자르기는 케이크를 넓이가 0이 아닌 두 부분으로 나눕니다.

모든 테스트 케이스에 걸친 자르기의 총 횟수는 $10\,000$을 넘지 않습니다.

각 테스트 케이스마다 한 줄에 실수 $P$ ($0 \leq P \leq 100$)를 소수점 아래 6자리까지 출력하고, 그 뒤에 \% 기호를 붙입니다. $P$는 앨리스가 각 자르기의 쪽을 최적으로 고를 때 먹을 수 있는 케이크의 백분율입니다. $P$가 정답과 $0.000002\%$ 이하로 차이 나면 정답으로 인정합니다.