你一定很熟悉「公平切蛋糕」的方案：一個人將蛋糕切成兩半，另一個人選擇他想吃的那一半。這個方案被認為是公平的，因為結果上沒有任何一方能聲稱自己拿到了較小的那塊。

然而，在 Alice 家裡，規則是由她制定的——而且這些規則絕對稱不上公平。她命令她的弟弟 Bob 切 $n$ 刀而不是一刀。現在，對於每一刀，Alice 都可以選擇其中一側，並吃掉該側所有的蛋糕。在 Alice 處理完所有的切痕後，Bob 才能吃剩下的部分。

蛋糕在笛卡爾平面上表示為一個正方形（當然，實際上它是一個長方體，但我們假設所有的切痕都垂直於表面），其邊長為 $M$。Bob 剛剛切了 $n$ 刀，現在輪到 Alice 做出選擇。請計算如果 Alice 明智地選擇，她總共能吃到多少蛋糕。

輸入格式

輸入的第一行包含測試案例的數量 $z$ ($1 \le z \le 500$)。接著是各個測試案例的描述。

每個測試案例的第一行包含兩個整數 $n$ ($1 \le n \le 4000$) 和 $M$ ($1 \le M \le 1000$)，分別代表切痕的數量和蛋糕的邊長。蛋糕是一個對角頂點位於 $(0, 0)$ 和 $(M, M)$ 的正方形。

接下來有 $n$ 行，第 $i$ 行包含三個整數 $A_i$、$B_i$ 和 $C_i$ ($-1000 \le A_i, B_i \le 1000, -10^6 \le C_i \le 10^6, A_i^2 + B_i^2 > 0$)，這些整數定義了第 $i$ 刀的直線方程式 $A_ix + B_iy + C_i = 0$。

更精確地說，Alice 得到了一組 $n$ 個直線方程式。對於每個方程式，她需要將 $=$ 運算子替換為 $\le$ 或 $\ge$，從而得到一個半平面方程式。蛋糕與這 $n$ 個半平面交集的部分，就是 Alice 可以吃掉的範圍。

每一刀都將蛋糕切成兩個面積非零的部分。

所有測試案例中的切痕總數不超過 $10\,000$。

輸出格式

對於每個測試案例，輸出單行包含一個實數 $P$ ($0 \le P \le 100$)，保留小數點後 6 位，並在後面加上「%」符號。這代表如果 Alice 對所有切痕都做出最佳選擇，她所能吃到的蛋糕百分比。如果你的答案與正確百分比的誤差不超過 $0.000002\%$，則視為正確。

範例

輸入 1

1
2 1000
0 1 -750
1 0 -750

輸出 1

93.750000%