Vous connaissez sûrement le principe du partage équitable d'un gâteau, où une personne coupe le gâteau en deux et l'autre choisit la part qu'elle préfère manger. Cette solution est censée être équitable car aucun des participants ne peut prétendre avoir reçu la plus petite part.

Chez Alice, c'est elle qui dicte les règles, et elles ne sont certainement pas censées être équitables. Elle ordonne à son jeune frère, Bob, de faire $n$ coupes plutôt qu'une seule. Maintenant, pour chaque coupe, Alice choisit l'un des côtés et mange tout le gâteau de ce côté. Après avoir passé en revue toutes les coupes, Bob mange le reste.

Le gâteau est représenté par un carré dans le plan cartésien (il s'agit en réalité d'un parallélépipède, bien sûr, mais nous supposons que toutes les coupes sont perpendiculaires à la surface) de côté $M$. Bob vient de faire $n$ coupes et il est maintenant temps pour Alice de faire ses choix. Déterminez quelle quantité de gâteau elle pourra manger si elle choisit judicieusement.

Entrée

La première ligne de l'entrée contient le nombre de cas de test $z$ ($1 \le z \le 500$). Les descriptions des cas de test suivent.

La première ligne de chaque cas de test contient deux entiers $n$ ($1 \le n \le 4\,000$) et $M$ ($1 \le M \le 1000$) — le nombre de coupes et la longueur du côté du gâteau. Le gâteau est un carré dont les sommets opposés sont situés aux points $(0, 0)$ et $(M, M)$.

Suivent ensuite $n$ lignes, la $i$-ième contenant trois entiers $A_i$, $B_i$ et $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$), qui définissent l'équation de droite $A_ix + B_iy + C_i = 0$ de la $i$-ième coupe.

Plus précisément, Alice reçoit un ensemble de $n$ équations de droite. Pour chaque équation, elle doit remplacer l'opérateur $=$ par soit $\le$, soit $\ge$, obtenant ainsi l'équation d'un demi-plan. L'intersection du gâteau avec l'intersection de $n$ tels demi-plans est ce qu'Alice sera autorisée à manger.

Chaque coupe divise le gâteau en deux parties d'aire non nulle.

Le nombre total de coupes dans tous les cas de test ne dépasse pas $10\,000$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un nombre réel $P$ ($0 \le P \le 100$) avec 6 chiffres après la virgule, suivi du signe « % » — le pourcentage du gâteau qu'Alice pourra manger si elle choisit tous les côtés des coupes de manière optimale. Votre solution sera acceptée si $P$ diffère du pourcentage correct d'au plus $0{,}000002\,\%$.

Exemples

Entrée 1

1
2 1000
0 1 -750
1 0 -750

Sortie 1

93.750000%