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

USU Championship 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Football and Lie

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

Input

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.

Output

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”.

Samples

inputoutput
3
-1 1 0
1 -1 -1
0 1 -1
0 0 1
3 0 3
1 0 0
5
-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
Impossible
Problem Author: Sergey Pupyrev
Problem Source: The XIth USU Programing Championship, October 7, 2006
To submit the solution for this problem go to the Problem set: 1485. Football and Lie