(Almost) Fair Cake-Cutting
You are surely familiar with the fair cake-cutting scheme, where one person cuts the cake in two and the other person gets to choose which part they would prefer to eat. This solution is supposed to be fair as neither of the participants can claim to have received the smaller part as the result.
Well, at Alice's, it is her who dictates the rules - and they are most certainly not supposed to be fair. She orders her younger brother, Bob, to make n cuts rather than one. Now, for every cut, Alice chooses one of the sides and eats all the cake at this side. After she finishes going through all the cuts, Bob gets to eat the rest.
The cake is represented as a square on the Cartesian plane (it is actually a cuboid, of course, but we assume all the cuts to be perpendicular to the surface) with side length m. Bob has just made n cuts and now it is time for Alice to make her choices. Determine how much cake will she be able to eat if she chooses wisely.
Input
The first line contains the number of test cases z (1 ≤ z ≤ 500). The descriptions of the test cases follow.
The first line of every test case contains two integers n (1 ≤ n ≤ 4000) and m (1 ≤ m ≤ 1000) - the number of cuts and the cake's side length. The cake is a square with its opposing vertices located in points (0, 0) and (m, m).
Then follow n lines, the i-th of them containing three integers a[i], b[i] and c[i] (-1000 ≤ a[i], b[i] ≤ 1000, -10^6 ≤ c[i] ≤ 10^6, a[i]^2 + b[i]^2 > 0), which define the line equation a[i] x + b[i] y + c[i] = 0 of the i-th cut.
More precisely, Alice is given a set of n line equations. For each equation, she needs to replace the = operator with either ≤ or ≥, obtaining a half-plane equation. The intersection of the cake with the sum of n such half-planes is what Alice will be allowed to eat.
Each cut splits the cake into two parts of non-zero area each.
The total number of cuts in all test cases does not exceed 10 000.
Output
For each test case output a single line containing a real number p (0 ≤ p ≤ 100) with 6 decimal digits, followed by the % sign - the percentage of the cake which Alice will be able to eat if she chooses all sides of the cuts optimally. Your solution will be accepted if p differs from the correct percentage by no more than 0.000002%.