Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Uncle Jeff owns a glass shop, which sells glass panes for windows and picture frames. As you probably know, a glass pane can only be cut if the cut goes from edge to edge of the pane in a straight line. The figure below shows how a glass pane can be cut into three smaller glass panes.

The input contains several test cases. The first line of a test case contains an integer $N$ indicating the number of windows and picture frames in the test $(2 \leq N \leq 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)$ represent the lower-left and upper-right coordinates marked by uncle Jeff on the big glass pane ($−5000 \leq X_1, Y_1, X_2, Y_2 \leq 5000$; $X_1 \lt X_2$ and $Y_1 \lt Y_2$). You should assume the following of each test case:

For each test case in the input your program must produce an ordered list of cuts that must be performed to separate the big glass pane into the desired smaller panes. Each cut must appear in a different line. A cut is described by four integers $X_1, Y_1, X_2, Y_2$, where $(X_1, Y_1)$ and $(X_2, Y_2)$ specify the endpoints of the cut, with $X_1 \lt X_2$ and $Y_1 = Y_2$ for a horizontal cut and $X_1 = X_2$ and $Y_1 \lt Y_2$ for a vertical cut. As more than one ordering of cuts may be possible, your program must print the list in a particular order. If at some point more than one cut is possible, print first the cut with smaller $X_1$; if more than one cut is still possible, print first the one with smaller $Y_1$. Print a blank line after each test case list.