ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Open Ural FU Championship 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Nanotechnologies

Time limit: 1.0 second
Memory limit: 64 MB
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

inputoutput
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
To submit the solution for this problem go to the Problem set: 1867. Nanotechnologies