Problem I
Line Segment Intersection

Input

The first line of input contains an integer $n$ ($n\le 10000$) giving the number of test cases. Then follow $n$ lines each containing 8 integers $x_1{y}_1{x}_2{y}_2{x}_3{y}_3{x}_4{y}_4$, indicating a line segment from $(x_1,y_1)$ to $(x_2,y_2)$, and a line segment from $(x_3,y_3)$ to $(x_4,y_4)$. Coordinates have absolute value at most 10000.

Output

For each test case, output the intersection between the two line segments in the following format:

• If the intersection is empty (i.e. the segments do not intersect), output the word “none”.

• If there is a unique intersection point $(X,Y)$, output the numbers $X$ and $Y$ separated by a single space.

• If the intersection is itself a line segment between two points $(X1,Y1)$ and $(X2,Y2)$, output the numbers $X_1{Y}_1{X}_2{Y}_2$ separated by spaces, in that order. Pick the point with smallest $x$-coordinate as the first point, or the point with smallest $y$-coordinate if both have the same $x$-coordinate.

Numbers should be given with 2 decimals of precision.

5
-10 0 10 0 0 -10 0 10
-10 0 10 0 -5 0 5 0
1 1 1 1 1 1 2 1
1 1 1 1 2 1 2 1
1871 5789 216 -517 189 -518 3851 1895

0.00 0.00
-5.00 0.00 5.00 0.00
1.00 1.00
none
221.33 -496.70