Bạn chắc hẳn đã quen thuộc với phương thức chia bánh công bằng, nơi một người cắt bánh thành hai phần và người kia được chọn phần họ muốn ăn. Giải pháp này được coi là công bằng vì không ai trong số những người tham gia có thể phàn nàn rằng mình nhận được phần nhỏ hơn.

Tuy nhiên, tại nhà của Alice, cô ấy là người đặt ra luật lệ – và chúng chắc chắn không hề công bằng. Cô ra lệnh cho em trai mình, Bob, thực hiện $n$ nhát cắt thay vì một. Bây giờ, với mỗi nhát cắt, Alice chọn một trong hai phía và ăn toàn bộ phần bánh ở phía đó. Sau khi cô ấy thực hiện xong tất cả các lựa chọn, Bob sẽ được ăn phần còn lại.

Chiếc bánh được biểu diễn dưới dạng một hình vuông trên mặt phẳng tọa độ Descartes (thực tế nó là một khối hộp, nhưng chúng ta giả định tất cả các nhát cắt đều vuông góc với bề mặt) với độ dài cạnh là $M$. Bob vừa thực hiện $n$ nhát cắt và bây giờ là lúc Alice đưa ra lựa chọn của mình. Hãy xác định lượng bánh cô ấy có thể ăn được nếu cô ấy chọn một cách khôn ngoan.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số lượng bộ test $z$ ($1 \le z \le 500$). Các mô tả của các bộ test sẽ theo sau.

Dòng đầu tiên của mỗi bộ test chứa hai số nguyên $n$ ($1 \le n \le 4000$) và $M$ ($1 \le M \le 1000$) – số lượng nhát cắt và độ dài cạnh của chiếc bánh. Chiếc bánh là một hình vuông với các đỉnh đối diện nằm tại các điểm $(0, 0)$ và $(M, M)$.

Tiếp theo là $n$ dòng, dòng thứ $i$ chứa ba số nguyên $A_i$, $B_i$ và $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$), xác định phương trình đường thẳng $A_ix + B_iy + C_i = 0$ của nhát cắt thứ $i$.

Cụ thể hơn, Alice được cung cấp một tập hợp gồm $n$ phương trình đường thẳng. Với mỗi phương trình, cô ấy cần thay thế toán tử $=$ bằng $\le$ hoặc $\ge$, để thu được phương trình nửa mặt phẳng. Phần giao của chiếc bánh với tổng của $n$ nửa mặt phẳng như vậy là phần bánh mà Alice được phép ăn.

Mỗi nhát cắt chia chiếc bánh thành hai phần có diện tích khác không.

Tổng số nhát cắt trong tất cả các bộ test không vượt quá $10\,000$.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng chứa một số thực $P$ ($0 \le P \le 100$) với 6 chữ số thập phân, theo sau là ký hiệu '%', biểu thị tỷ lệ phần trăm chiếc bánh mà Alice có thể ăn được nếu cô ấy chọn tất cả các phía của các nhát cắt một cách tối ưu. Giải pháp của bạn sẽ được chấp nhận nếu $P$ sai lệch so với tỷ lệ phần trăm chính xác không quá $0.000002\%$.

Ví dụ

Dữ liệu vào 1

1
2 1000
0 1 -750
1 0 -750

Dữ liệu ra 1

93.750000%