Specialists at the Nanotechnology Lab at the Ural Federal University work on developing a computer that would operate at the level of individual atoms. They have recently learned that n tantalum atoms arranged on a plane in a special way can be used for constructing a quantum computer with earlier unattainable characteristics.
Unfortunately, the theory describes only some of the physical characteristics of such a system of atoms. The physicists must find an arrangement of atoms that would provide the necessary effect. The scanning tunneling microscope used in the project can place tantalum atoms only at points whose coordinates are integers with absolute values not exceeding 106; the unit of the coordinate system is one nanometer.
The scientists ask you to help them determine the coordinates of the atoms. They have eliminated the unnecessary physical information, providing you only with the squared distances between all the pairs of atoms.
Input
The first line contains the total number of atoms n (2 ≤ n ≤ 100).
In the following n lines you are given an n × n matrix aij with integer elements.
The number aij is the required squared distance between atoms numbered
i and j (0 ≤ aij ≤ 109; aij = aji; aii = 0).
Output
If there is an arrangement satisfying the given matrix of squared distances, output n lines.
The ith line must contain the coordinates of the ith atom; they must be integers with
absolute values not exceeding 106. If there are several possible answers, output any of them.
If it is impossible to arrange the atoms as required, output “Impossible”.
Samples
input | output |
---|
3
0 1 4
1 0 1
4 1 0
| 0 0
1 0
2 0
|
3
0 1 5
1 0 1
5 1 0
| Impossible
|
3
0 1 0
1 0 1
0 1 0
| 5 -5
5 -4
5 -5
|
Problem Author: Sergey Pupyrev (prepared by Ivan Burmistrov)
Problem Source: Open Ural FU Championship 2011