Let us remind that the number of teams participating
in the table-football tournament among programmers
in the city of Petrozavodsk was N.
In the course of the tournament, each team played with each team exactly once. For each win a team earned 3 points, for a draw it earned 1 point, and for a defeat a team got 0 points. After the tournament, each team's captain made several declarations of the type: “We earned points in the match with team X”, or “We didn't earn points in the match with team X”. It is not necessary that each captain made declarations concerning all other teams. The camp's organizers understood that some captains always lied and others always told the truth.
Using this information, restore the results of the
The first line of the input contains the number of teams
1 ≤ N ≤ 100. Then there is the matrix of declarations A in the following form. There are N lines containing N numbers each, and these numbers are 0, 1, or –1.
If Aij = 1, then the captain of the i-th team declared that his team had earned points
in the match against the j-th team.
If Aij = 0, then the captain of the i-th team declared that his team had not earned points in the match against the j-th team.
And if Aij = –1, it means that the captain of the i-th team abstained from a declaration concerning the match against the j-th team. It is guaranteed that Aii = –1 for each i.
If there exists a solution, then output a matrix B of size N × N in which Bij is the number of points awarded to the i-th team for the match against the j-th team. If there are many solutions, you may output any of them. If there is no solution, then output “Impossible”.
-1 1 0
1 -1 -1
0 1 -1
0 0 1
3 0 3
1 0 0
-1 1 1 0 0
0 -1 1 -1 -1
1 0 -1 -1 -1
0 -1 -1 -1 1
1 -1 -1 0 -1
Problem Author: Sergey Pupyrev
Problem Source: The XIth USU Programing Championship, October 7, 2006