D. 3D
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

$$$n$$$ points $$$a_1, a_2, ..., a_n$$$ are randomly generated inside a cube of size 1.

You are given a matrix $$$d$$$ with $$$d_{i,j}=d_{j,i}=dist(a_i, a_j)+rand(-0.1..0.1)$$$ and $$$d_{i,i}=0$$$. Here $$$dist(p, q)$$$ is the distance between points $$$\sqrt{(p_x-q_x)^2+(p_y-q_y)^2+(p_z-q_z)^2}$$$ and $$$rand(-0.1..0.1)$$$ is a random shift chosen uniformly from interval $$$[-0.1..0.1]$$$. Shifts for different pairs of points are chosen independently.

You need to construct a list of points $$$b_1, b_2, ..., b_n$$$ such that $$$\forall_{i, j} |dist(b_i, b_j)-d_{i,j}| \le 0.1$$$.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 10$$$) — the number of points.

The next $$$n$$$ lines contain the description of matrix $$$d$$$. The $$$i$$$-th line contains $$$n$$$ real values $$$d_{i,j}$$$ ($$$-0.1 \le d_{i,j} \le \sqrt{3}+0.1$$$). Each value is given with 6 digits after the decimal point.

It is guaranteed that $$$d_{i,i}=0$$$ and $$$d_{i,j}=d_{j,i}$$$.

Output

Print $$$n$$$ lines describing the points. $$$i$$$-th line should contain three real numbers $$$x_i$$$ $$$y_i$$$ $$$z_i$$$ ($$$-10.0 \le x_i, y_i, z_i \le 10.0$$$).

Example
Input
4
0.000000 0.758400 0.557479 0.379026
0.758400 0.000000 0.516608 0.446312
0.557479 0.516608 0.000000 0.554364
0.379026 0.446312 0.554364 0.000000
Output
0.210269 0.581333 0.000000
0.090086 0.000000 0.458722
0.000000 0.498388 0.501723
0.204618 0.204262 0.075724
Note

This problem has $$$30$$$ test cases.