Artistica

All submissions for this problem are available.
The students are painting their imaginations on the canvas. One of the students Zetti likes only line segments and he has given a poster composed of only straight line segments to the authorities. But he has violated the frame dimensions asked for poster and has only the last few minutes to rectify this mistake. He knows that you are good at programming and has approached you for help.
The task for the problem is simple. You will be given a pair of points in the 2D plane representing the lower left(x_{1}, y_{1}) and the upper right(x_{2}, y_{2}) corners of the frame. There are N line segments and you know the coordinates of its end points. You need to print the end points of the maximum length segment that will be completely inside (or on the boundary) of the frame. If the line segment will always be outside the frame print “OUTSIDE” instead. Below is the graph of the sample test case. (Not to scale).
Input
The first line of input consists of the number of test cases T. The description of T test cases follows. Each test case begins with five integers on a line x_{1} y_{1} x_{2} y_{2} N (all separated by single space). Then follows N lines each consisting of a four integers a_{x} a_{y} b_{x} b_{y} denoting the end points of the line segment. It is guaranteed that the length of any line segment is greater than zero and the area of the frame is greater than 0.
Output
For each test case T, you need to print N lines. Each line should contain the end points of the truncated line segment such that it is within (or on the boundary) of the frame. These end points must be sorted by its abscissa value and in case the x value of both points are same, then the ordinate value. If no part of the segment can be inside the frame the print “OUTSIDE”.
Note that the answers would be accepted only if it has an error of less than 10^{6}.
Constraints
T≤10
0<N≤10^{5}
The absolute value of all given points is less than equal to 10^{9}
Example
Input: 1 1 1 5 5 3 1 6 4 7 2 4 2 2 3 3 7 3 Output: OUTSIDE 2 2 2 4 3 3 5 3
Explanation
See the image above for explanations.
Author:  phantom11 
Tags  phantom11 
Date Added:  30032013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, GO 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 