Wallpapering#665
During an apartment renovation, one of the kitchen walls needed (N-1) rectangular ventilation openings with sides parallel to the axes (1 \leq N \leq 100). If a new opening overlapped with an existing one, only the untouched part of the new rectangle would be cut out.
After the renovation, the next step is wallpapering. You can order up to (2N-1)^2 rectangular wallpaper pieces of arbitrary sizes (with a non-zero area) from the nearby store. The goal is to cover the wall with these wallpaper pieces in such a way that:
The ventilation openings are not covered, even partially.
No two wallpaper pieces overlap (but they may touch at the edges).
There are no uncovered areas left on the wall.
Consider a Cartesian coordinate system where the axes are parallel to the sides of the rectangles (the wall and the openings).
First, the integer (1 \leq N \leq 100) is given. Then, rectangles are provided. The first rectangle describes the wall, and the remaining (N - 1) rectangles describe the ventilation openings in the order in which they appear. All rectangle sides are parallel to the axes. Each rectangle is defined by the coordinates x_1, y_1, x_2, y_2 of its lower left and upper right corners. The coordinates are integers with absolute value not exceeding , and x_1 < x_2, y_1 < y_2.
The rectangles representing the ventilation openings may intersect or touch each other, as might be necessary in the renovation. All ventilation openings are fully contained within the wall, i.e., they do not extend beyond the first rectangle.
First, print the number of wallpaper pieces to order from the store ( must not exceed (2N-1)^2). Then print the wallpapering plan: rectangles giving the positions of the ordered pieces. For each rectangle, print the coordinates of its lower left and upper right corners. All coordinates must be integers. It is guaranteed that a solution exists.
If more than one solution exists, print any of them.
Example 1