Potholes

You are competing with another company for a city contract to fill the potholes in the city streets.

To decide the winner, the city holds a contest in a rectangular parking lot that contains many potholes and measures which company works faster.

You must stretch a rope in a straight line from one side of the lot across to the opposite side, splitting the lot into two smaller rectangles. Your opponent then chooses which of the two sides to work in, and you take the other side. You therefore want to place the rope so that the amount of work — the total area of the potholes — is as nearly equal as possible on the two sides.

Potholes are modeled as circles. No two potholes overlap, and no pothole overlaps an edge of the lot. Your rope may not cross a pothole, but it may be tangent to a pothole, to another pothole, or to an edge of the lot.

The input consists of one or more problem sets.

Each problem set is given as:

• One line with the width $x$ and the height $y$ of the parking lot, as two positive floating-point numbers.
• Two or more lines, each describing one pothole with three non-negative floating-point numbers: the $x$ and $y$ coordinates of the pothole's center, followed by its radius. The origin of the coordinate system is a corner of the lot.
• A line containing three zeros separated by spaces (0 0 0), which marks the end of that problem set.

After the last problem set, a line containing two zeros separated by spaces (0 0) — appearing where the next lot description would begin — marks the end of all input.

For each problem set, determine where to place the rope so that the total pothole area on each side of the rope is as nearly equal as possible. The rope may not pass through any pothole, though it may be tangent to potholes.

For each problem set, print one line

x1 y1 x2 y2

where $(x_1, y_1)$ and $(x_2, y_2)$ are the two points at which the rope meets the boundary of the lot. Order the two points so that $x_1 \le x_2$ and $y_1 \le y_2$. Print every coordinate to exactly one decimal place, with single spaces between values.

Choose these points so that the rope divides the potholes into two groups whose total areas are as nearly equal as possible.

If more than one rope placement makes the pothole areas equally close, break the tie in the following order:

1. Prefer the placement that most nearly divides the parking lot itself into two equal areas.
2. If a tie remains, prefer the rope that meets the x-axis of the lot (that is, a rope parallel to the y-axis).
3. If a tie still remains, prefer the smaller x-coordinate.