Cutting Edge

Uncle Jeff owns a glass shop that sells glass panes for windows and picture frames. As you may know, a glass pane can only be cut along a straight line that runs from one edge of the pane all the way to the opposite edge. The figure below shows how a single glass pane can be cut into three smaller panes.

Uncle Jeff usually works as follows. He first collects several orders for small rectangular panes (for windows or picture frames). He then marks the position of each small rectangle on one big rectangular pane so that no two marked rectangles overlap. Finally, he makes a sequence of horizontal and vertical cuts — each running straight from one edge of the current piece to the opposite edge — until every customer's pane has been produced.

Because this last phase (the actual cutting of the big pane) is the most boring thing imaginable, Uncle Jeff asks for your help. Given the big rectangular pane and the lower-left and upper-right coordinates of every marked rectangle, determine the order in which the edge-to-edge cuts should be made. This list of cuts will be fed to a machine that performs the boring cutting for him.

The input contains several test cases. The first line of each test case contains an integer $N$, the number of windows and picture frames ($2 \le N \le 2000$). Each of the next $N$ lines contains four integers $X_1$, $Y_1$, $X_2$, $Y_2$, where $(X_1, Y_1)$ and $(X_2, Y_2)$ are the lower-left and upper-right corners of a marked rectangle ($-5000 \le X_1, Y_1, X_2, Y_2 \le 5000$; $X_1 < X_2$ and $Y_1 < Y_2$).

For every test case you may assume the following:

• The marked rectangles do not overlap (though they may touch along their borders) and together they completely fill a big rectangular pane, wasting no glass. Hence the lower-left and upper-right corners of the big pane can be deduced from the rectangles' coordinates.
• The big pane can always be separated into the marked rectangles by a sequence of edge-to-edge cuts.

A line containing $N = 0$ marks the end of the input and must not be processed.

For each test case, output the ordered list of cuts needed to separate the big pane into the desired smaller panes. Print each cut on its own line as four integers $X_1$ $Y_1$ $X_2$ $Y_2$, the two endpoints of the cut, where:

• a horizontal cut has $Y_1 = Y_2$ and $X_1 < X_2$;
• a vertical cut has $X_1 = X_2$ and $Y_1 < Y_2$.

A cut can be made on the current piece only if it runs straight from one edge to the opposite edge without crossing the interior of any marked rectangle, thereby splitting that piece into two. Several cuts may be available at the same time; to make the answer unique, always perform the available cut with the smallest $X_1$, breaking ties by the smallest $Y_1$. Perform one cut at a time and re-evaluate after each cut, continuing until every piece is a single marked rectangle.

Separate the cut lists of consecutive test cases with a blank line.