(Майже) Справедливе розрізання торта
Ви, напевно, знаєте про справедливий спосіб розділити торт, коли одна людина розрізає його навпіл, а інша обирає, яку частину з'їсти. Це вважається справедливим, оскільки жоден з учасників не може сказати, що отримав меншу частину.
Але Аліса встановлює свої правила, і вони точно не повинні бути справедливими. Вона наказує своєму молодшому братові Бобу зробити n розрізів, а не один. Тепер, для кожного розрізу, Аліса обирає одну зі сторін і з'їдає весь торт з цього боку. Після того, як вона закінчить, Боб з'їдає залишок.
Торт представлений у вигляді квадрата на декартовій площині (насправді це прямокутний паралелепіпед, але ми припускаємо, що всі розрізи перпендикулярні поверхні) з довжиною сторони m. Боб щойно зробив n розрізів, і тепер настав час Алісі зробити свій вибір. Визначте, скільки торта вона зможе з'їсти, якщо зробить правильний вибір.
Вхідні дані
Перша строка містить кількість тестів z (1 ≤ z ≤ 500). Далі йдуть описи тестів.
Перша строка кожного набору вхідних даних містить два цілі числа n (1 ≤ n ≤ 4000) і m (1 ≤ m ≤ 1000) - кількість розрізів і довжина сторони торта. Торт являє собою квадрат, протилежні вершини якого розташовані в точках (0, 0) і (m, m).
Потім слідують n рядків, i-й з яких містить три цілі числа a[i], b[i] і c[i] (-1000 ≤ a[i], b[i] ≤ 1000, -10^6 ≤ c[i] ≤ 10^6, a[i]^2 + b[i]^2 > 0), які визначають лінійне рівняння a[i] x + b[i] y + c[i] = 0-го розрізу.
Алісі надається набір з n лінійних рівнянь. Для кожного рівняння їй потрібно замінити оператор = на ≤ або ≥, отримавши рівняння півплощини. Перетин торта з сумою n таких півплощин - це те, що Аліса зможе з'їсти.
Кожен розріз ділить торт на дві частини ненульової площі кожна.
Загальна кількість розрізів у всіх тестах не перевищує 10 000.
Вихідні дані
Для кожного тесту виведіть один рядок, що містить дійсне число p (0 ≤ p ≤ 100) з 6 десятковими цифрами, за яким слідує символ % - відсоток торта, який Аліса зможе з'їсти, якщо оптимально вибере всі сторони розрізів. Ваше рішення буде прийнято, якщо p відрізняється від правильного відсотка не більше ніж на 0.000002%.