Tsinghua University has many academic buildings, but due to the heavy academic workload of students, there are many people studying independently, especially before final exams, when study spaces in the buildings are still in short supply. To welcome the 2008 Beijing Olympics and improve study conditions for students, the school decided to build the Seventh Academic Building.

The Seventh Academic Building consists of several small academic buildings (referred to as segments in the figure below) and a large bicycle parking lot. The top view of each academic building is a triangle. The bicycle parking lot of the Seventh Academic Building is a large triangle that contains all the small academic buildings. As shown in the figure below:

Since the total area of the school is limited, the land occupation of the Seventh Academic Building must be minimized, meaning the total area of the large triangle formed by all the academic buildings and the bicycle parking lot must be as small as possible.

Given the size of the top view of each small academic building (provided in coordinate form), you are required to design the scope of the parking lot (the parking lot area can be zero). You can translate, rotate, and flip the positions of these small academic buildings, but you cannot change their size or shape, such that the top view of the parking lot is a large triangle, and every small academic building is inside the parking lot (Note: in the answer, the edges of the top views of the small academic buildings can overlap, but the common area of any two small academic buildings must be 0).

You need to determine the coordinates of the top view of each academic building and the coordinates of the top view of the parking lot to minimize the total area they form.

Input

This is a submission-based problem; all input files triangle*.in are already in the directory.

The first line of the input file contains an integer $N$, representing the number of small academic buildings. The next $N$ lines each contain six real numbers separated by spaces. The $i$-th line represents the initial coordinates of the three points of the top view of the $i$-th small academic building: $x_0, y_0, x_1, y_1, x_2, y_2$.

(Note: The initial top views of the small academic buildings may overlap.)

Output

The output file triangle*.out should contain $N+1$ lines. The first line contains six real numbers $x_0, y_0, x_1, y_1, x_2, y_2$ separated by spaces, representing the coordinates of the top view of the bicycle parking lot you designed, which can be at any position on an infinite plane.

The next $N$ lines each contain six real numbers $x_0, y_0, x_1, y_1, x_2, y_2$ separated by spaces. The six real numbers in the $i$-th line represent the final placed position of the $i$-th small academic building. The output order of the small academic buildings in the output file must be the same as their input order in the input file.

Examples

Input 1

2
-1 0 0 0 0 1
1 0 0 0 0 1

Output 1

0 1 -1 0 1 0
-1 0 0 0 0 1
1 0 0 0 0 1

Note 1

The two input academic buildings are as follows: Academic building segment 1 $(-1, 0, 0, 0, 0, 1)$: Academic building segment 2 $(1, 0, 0, 0, 0, 1)$ They can be spliced into a large triangular parking lot (shown with thick lines), and the area of the parking lot is zero. The final coordinates of the Seventh Academic Building $(0, 1, -1, 0, 1, 0)$.

Scoring

Each test case is scored individually.

For each test case, if your output file is invalid (e.g., incorrect file format, solution does not meet requirements), you will receive 0 points for that test case. Otherwise, let the area of the triangle in your output be $YourAns$.

If your answer is better than or equal to our answer, you will receive 10 points; otherwise, your score will be calculated according to the following formula:

$Score = 10 \times \frac{\text{OurAns}}{YourAns}$

Interaction

You can use the checker program to check your output. The format is:

./checker CaseNo

Where CaseNo is the number of the test case. For example, if you have already obtained the output triangle5.out for data 5, you can use the command ./checker 5 to test whether your output is valid. The checker will also output the total area occupied by your solution.

For the following errors, we will return:

(Note: If your output file is not formatted according to the standard, it may cause other problems.)

Note

Please keep the input files *.in and your output *.out safe and back them up in time to avoid accidental deletion.