Rectangle Outline

Given a series of rectangular obstacles, one per line. Rectangular obstacles can overlap each other. Each rectangular obstacle is specified as two points on 2D plane that specify the opposite corners of a rectangle. Your job is to calculate the outline of the coverage area of all rectangular.

If the outline is made up of more than one closed polyline, print "Oops!". Otherwise, output the answer as follows: The first output point has the smallest X coordinate and then smallest Y coordinate. The second point has the same X coordinate with the first point. Then output other points in outline order. You can see more details in Sample.

It's guarantee that every rectangle's sides are parallel to OX and OY. Any point on the 2D plane will not be the vertices of two rectangles at the same time.

The first line contain a integer $T$(no more than 10), the following is $T$ test case, for each test case:

The first line of each test case contains a integers n (1 $\le$ n $\le$ 100,000), number of rectangular obstacles.

Each of the next n lines contains 4 integers x1, y1, x2, y2 (1 $\le$ x1 < x2 $\le$ 1,000,000,000, 1 $\le$ y1 < y2 $\le$ 1,000,000,000) specify a rectangular obstacles.

It is guaranteed that the sum of all n does not exceed 700,000.

Output the answer as described previously.

3
2
1 1 3 3
2 2 4 4
4
1 2 2 5
3 2 4 5
2 1 3 3
2 4 3 6
2
1 1 2 2
3 3 4 4

8
1 1
1 3
2 3
2 4
4 4
4 2
3 2
3 1
Oops!
Oops!

2018 Multi-University Training Contest 6