L-Link doesn't want to cut tree_2025牛客国庆集训派对day8

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

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 $ABCD$ , you should calculate four distinct points $A'B'C'D'$ , which satisfies:

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

You need to calculate $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  --- the number of test cases.

Each test case contains  integers  --- the coordinates of points . The absolute value of all integers should not exceed .

输出描述:

For each test case, if there is at least a solution, print "Link doesn't cut tree!", then print 8 numbers, representing  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 .

示例1

输入

复制

3
-2 1 2 1 2 -1 -2 -1
8 -2 -6 -4 -7 1 -2 4
-4 4 4 4 8 -2 -6 -3

输出

复制

Link doesn't cut tree!
-4 0 0 2 4 0 0 -2
Link cut tree!
Link doesn't cut tree!
-12 0 0 6 12 0 0 -6

说明

Case 1:
Case 2:
Case 3: