Problem B. Bottom of the sea ≡

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 (a_x, a_y) − (b_x, b_y).

Suddenly, a representative of the Ministry of Defense showed up, and declared that the rectangular area with coordinates (c_x, c_y) − (d_x, d_y) 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 a_x a_y b_x b_y c_x c_y d_x d_y.

Output file format

Output file should contain minimum number of submersions M followed by M groups of 4 integers x_i y_i u_i v_i — 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

Sample tests

-10 -10 10 10
0 0 20 20

2
-10 -10 10 0
-10 0 0 10

1 2 3 4
10 11 12 13

1
1 2 3 4

-1 -1 1 1
-2 -2 2 2

0