H. Hatch

You need some parts manufactured for your zombie protection suit. These parts are made of steel, and steel can not be cut in your laser CNC. Unfortunately most of the craftsmen have already left the city. The ones you can still contact are old fashioned guys, following all the good tradition: they do not work from CAD files but from printouts. No problem, you can print all your drawings - as long as you have ink in your printer.

The zombie apocalypse reveals a lot of suboptimal system features in all the software and hardware around you, and your CAD program is not an exception. You need to hatch (fill using parallel lines) large polygons on those drawings, but your CAD system does not optimize the hatch pattern for saving ink. You obviously can not afford wasting ink like that!

   few polygons hatched on a real drawing

You are given a number of polygons, that make up your drawing. Only adjacent sides of a polygon touch, and the circumference of different polygons never intersects. These polygons separate the plane into shapes and holes: the outermost polygons are shapes, the ones contained immediately in these are holes, the polygons inside those are again shapes, and so on.

Your CAD program will hatch the shapes (but not the holes) with horizontal lines of distance D. (Horizontal means parallel to the x axis.) If a side of a polygon is horizontal, the program will not draw a hatch line over it. If a hatch line touches a vertex of the polygon, it still counts as one line.

Your task is to optimize the offset of these lines to minimize total number of hatch lines.


First line contains two integers: N, the number of polygons, and D, the distance between two adjacent hatch lines. Then the descriptions of the polygons follow. First line of each polygon is a single integer, K_i, the number of vertices in the i-th polygon. The next K_i line contains two integers, the x and y coordinates of the vertices. Vertices can be ordered clockwise or counter-clockwise.


N floats, the best offset for each polygon. If more than one offset gives the same best result, any of them is accepted. If a polygon is a hole, any number can be written. Each number (X) must be 0 <= X < D

Example input

2 10
0 0
50 10
0 46
20 20
5 8
10 6

Example output

(Explanation: for the first value, "0", "6", "0.", "6.", "0.0000" or any other format of 0 or 6 would be accepted, they all need 5 hatch lines. For the second value, anything between 0 and 10 would be accepted)