Single Cut of Failure

The Intrusion and Crime Prevention Company builds intrusion detection systems for homes and businesses. The International Collegiate Programming Contest, which happens to share the same initials, is thinking about hiring the company to secure the room that holds the problem set for next year's world finals.

The contest staff wants to stop the intrusion attempts of past years: rappelling down the outside of the building to reach a window, crawling through air ducts, impersonating a contest official, and the creative use of an attack submarine. For that reason the problems will sit in a room with a single door and no other exit.

The company proposes sensors on the four sides of the door. Pairs of sensors are joined by wires, and every wire runs in a straight line across the door. When somebody opens the door, each connected pair detects it and sounds an alarm.

The design has one flaw. An intruder can cut the wires before opening the door. A cut is a straight segment whose two ends lie on the boundary of the door, and the two ends have to lie on different sides of the door. A cut destroys every wire it crosses. To measure how safe the system is, find the smallest number of cuts that together cross all of the wires.

The door is the rectangle with corners $(0, 0)$, $(w, 0)$, $(w, h)$ and $(0, h)$.

Figure 1 draws the wires of the two examples and, for each of them, a set of cuts of the smallest possible size. The drawn cuts are one correct answer, not the specific answer this problem asks for.

The first line contains three integers $n$, $w$ and $h$: the number of wires ($1 \le n \le 10^6$) and the width and the height of the door ($1 \le w, h \le 10^8$).

Each of the next $n$ lines contains four integers $x_1$, $y_1$, $x_2$ and $y_2$ ($0 \le x_1, x_2 \le w$, $0 \le y_1, y_2 \le h$), describing a wire that runs from $(x_1, y_1)$ to $(x_2, y_2)$. Both anchors of a wire lie on the boundary of the door and on two different sides of it. No anchor is a corner of the door, and all $2n$ anchor locations are distinct.

Print the smallest number of cuts on the first line. Then print the cuts, one per line, as four numbers $x_1$ $y_1$ $x_2$ $y_2$ meaning the cut from $(x_1, y_1)$ to $(x_2, y_2)$. One cut or two cuts are always enough, so the first line is 1 or 2.

Several sets of cuts can share the smallest size, so print the one described here. Measure a point of the boundary by the distance you walk along the boundary to reach it, starting at the corner $(0, 0)$ and going to $(w, 0)$, then to $(w, h)$, then to $(0, h)$, and back to $(0, 0)$. The whole boundary has length $2(w + h)$, and every wire anchor sits at an integer distance. Both ends of every cut you print sit at a half-integer distance, meaning a distance whose fractional part is exactly $0.5$. Such a point is never a corner and never an anchor.

If a single cut crosses all of the wires, print 1 and then that cut. Write $p$ for the smaller and $q$ for the larger of the two distances of its ends. Among all cuts whose ends sit at half-integer distances, lie on two different sides and cross every wire, take the one with the smallest $p$, and among those the one with the smallest $q$. Print the end at distance $p$ first.

If no single cut crosses all of the wires, print 2 and then exactly these two cuts in this order: the cut from $(0.5, 0)$ to $(w - 0.5, h)$, then the cut from $(w, 0.5)$ to $(0, h - 0.5)$.

Print a coordinate as an integer when it is a whole number, and with exactly one digit after the decimal point otherwise.