8988: link doesn't want to cut tree

link has a convex quadrilateral farm, and he planted four trees at the four vertices of the farm to mark it.

Now link wants to expand his farm, and he has some requirements for the new farm:

• The new farm should be a diamond shape, which is a quadrilateral with equal sides.
• The new farm area should be twice that of the original farm.
• link doesn't want to cut trees, so the four trees should be placed on each side of the new farm.

Formally, given a convex quadrilateral ABCDABCDABCD, you should calculate four distinct points A′B′C′D′A'B'C'D'A′B′C′D′, which satisfies:

•  A′B′C′D′A'B'C'D'A′B′C′D′ is a diamond shape, that is, ∣A′B′∣=∣B′C′∣=∣C′D′∣=∣D′A′∣|A'B'|=|B'C'|=|C'D'|=|D'A'|∣A′B′∣=∣B′C′∣=∣C′D′∣=∣D′A′∣.
•  SA′B′C′D′=2SABCDS_{A'B'C'D'}=2S_{ABCD}SA′B′C′D′=2SABCD.
•  Point $A$ is located on segment A′B′A'B'A′B′. Point $B$ is located on segment B′C′B'C'B′C′. Point $C$ is located on segment C′D′C'D'C′D′. Point $D$ is located on segment D′A′D'A'D′A′.

You need to calculate A′B′C′D′A'B'C'D'A′B′C′D′ or indicate that this is impossible.

Each test contains multiple test cases. The first line of input contains a single integer t(1≤t≤104)t(1\leq t\leq 10^4)t(1≤t≤104) --- the number of test cases.
Each test case contains $8$ integers xA,yA,xB,yB,xC,yC,xD,yDx_A,y_A,x_B,y_B,x_C,y_C,x_D,y_DxA,yA,xB,yB,xC,yC,xD,yD --- the coordinates of points A,B,C,DA,B,C,DA,B,C,D. The absolute value of all integers should not exceed 10410^4104.

For each test case, if there is at least a solution, print "link doesn't cut tree!", then print 8 numbers, representing xA′,yA′,xB′,yB′,xC′,yC′,xD′,yD′x_{A'},y_{A'},x_{B'},y_{B'},x_{C'},y_{C'},x_{D'},y_{D'}xA′,yA′,xB′,yB′,xC′,yC′,xD′,yD′ respectively.
If there is no possible solution, print "link cut tree!".
The answer would be considered correct if the absolute error of all conditions is no more than 10−510^{-5}10−5.