Вам наверняка знакома схема «честного» разрезания торта, при которой один человек разрезает торт на две части, а другой выбирает, какую часть он хочет съесть. Считается, что это решение справедливо, так как ни один из участников не может заявить, что получил меньшую часть.

Однако у Алисы правила диктует она сама, и они определенно не должны быть честными. Она приказывает своему младшему брату Бобу сделать $n$ разрезов вместо одного. Теперь для каждого разреза Алиса выбирает одну из сторон и съедает всю часть торта с этой стороны. После того как она закончит со всеми разрезами, Боб съедает остатки.

Торт представлен в виде квадрата на декартовой плоскости (на самом деле это параллелепипед, но мы предполагаем, что все разрезы перпендикулярны поверхности) со стороной $M$. Боб только что сделал $n$ разрезов, и теперь пришло время Алисе сделать свой выбор. Определите, какую часть торта она сможет съесть, если будет выбирать оптимально.

Входные данные

Первая строка входных данных содержит количество тестов $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$), которые определяют уравнение прямой $A_ix + B_iy + C_i = 0$ для $i$-го разреза.

Точнее, Алисе дается набор из $n$ уравнений прямых. Для каждого уравнения ей нужно заменить оператор $=$ на $\le$ или $\ge$, получив уравнение полуплоскости. Пересечение торта с пересечением $n$ таких полуплоскостей — это то, что Алисе будет позволено съесть.

Каждый разрез делит торт на две части ненулевой площади.

Общее количество разрезов во всех тестах не превышает $10\,000$.

Выходные данные

Для каждого теста выведите одну строку, содержащую вещественное число $P$ ($0 \le P \le 100$) с 6 знаками после запятой, за которым следует знак «%» — процент торта, который Алиса сможет съесть, если выберет стороны разрезов оптимально. Ваше решение будет принято, если $P$ отличается от правильного ответа не более чем на $0.000002\%$.

Примеры

Входные данные 1

1
2 1000
0 1 -750
1 0 -750

Выходные данные 1

93.750000%