Wallpapering
Major Pronin has decided to renovate his apartment. As part of the plan, he needs to create a series of rectangular ventilation openings with horizontal and vertical sides in one of the kitchen walls (1 ≤ N ≤ 100). If a new opening overlaps with an existing one, only the untouched portion of the new rectangle will be cut out.
After completing the renovation, the next step is wallpapering. Major Pronin can order up to (2N–1)^2 rectangular wallpaper pieces of any size, as long as they have a non-zero area, from the store across the street. The goal is to cover the wall with these wallpaper pieces while ensuring:
The ventilation openings remain completely uncovered.
No two wallpaper pieces overlap, although they can touch at the edges.
The entire wall is covered without any gaps.
Input
Consider a Cartesian coordinate system where the axes are aligned with the sides of the openings and the wall.
First, you will receive the number N (1 ≤ N ≤ 100), followed by the descriptions of N rectangles. The first rectangle specifies the position of the wall in this coordinate system, while the remaining (N–1) rectangles describe the positions of the ventilation openings in the order they were created. All rectangle sides are parallel to the coordinate axes. Each rectangle is defined by the coordinates of its lower left and upper right corners: x_1, y_1, x_2, y_2. The coordinates are integers not exceeding 31000 in absolute value, with x_1 < x_2 and y_1 < y_2.
The rectangles representing the ventilation openings may intersect or touch each other, as this might have been necessary during the renovation. All ventilation openings are contained within the wall, meaning they do not extend beyond the first rectangle.
Output
First, output the number of wallpaper pieces K that need to be ordered from the store (K should not exceed (2N–1)^2). Then, provide the wallpapering scheme: K rectangles representing the placement of the ordered pieces. For each rectangle, output the coordinates of its lower left and upper right corners. All coordinates must be integers. It is guaranteed that a solution exists.
If there are multiple valid solutions, you may output any one of them.