Problem B. Bottom of the sea

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

The Nearsea Institute of Underwater Studies decided to make a survey of the sea bottom.

The area where the survey takes place is represented by a rectangular grid. The x axis runs from west to east and the y axis runs from south to north.

A robotic underwater vehicle is used to perform the survey. The vehicle has a program which allows him to cover a rectangular part of the sea bottom defined by the coordinates of its south-west and north-east corners.

Initially it was planned for a robot to submerge once and survey a single rectangular area with coordinates (ax, ay) − (bx, by).

Suddenly, a representative of the Ministry of Defense showed up, and declared that the rectangular area with coordinates (cx, cy) − (dx, dy) contains secret military installations, and must not be visited by the vehicle.

It was decided to split the survey area into a smaller rectangles and perform a separate submersion for each of them. Rectangles must not intersect neither the restricted area nor each other and must cover all survey area except the restricted area.

Your program must find the splitting which requires minimal number of submersions.

Input file format

Input file contains 8 integers ax ay bx by cx cy dx dy.

Output file format

Output file should contain minimum number of submersions M followed by M groups of 4 integers xi yi ui vi — coordinates of the south-east and north-west corners of the area which should be covered by i-th submersion. If there is more than one optimal solution, output any of them.

Constraints

 − 109 ≤ ax < bx ≤ 109,  − 109 ≤ ay < by ≤ 109,  − 109 ≤ cx < dx ≤ 109,  − 109 ≤ cy < dy ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
-10 -10 10 10
0 0 20 20
2
-10 -10 10 0
-10 0 0 10
2
1 2 3 4
10 11 12 13
1
1 2 3 4
3
-1 -1 1 1
-2 -2 2 2
0

0.096s 0.009s 13