I. Transitive Closure
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider a square matrix $$$a$$$ of size $$$n$$$ consisting only of zeros and ones.

Apply the following algorithm to it: while there exist indices $$$i$$$, $$$j$$$, $$$k$$$ (not necessarily distinct) such that $$$a[i][j]=1$$$, $$$a[j][k]=1$$$, and $$$a[i][k]=0$$$, replace $$$a[i][k]$$$ with $$$1$$$. The resulting matrix is called the transitive closure of matrix $$$a$$$.

For the given matrix $$$a$$$, find a matrix $$$b$$$ such that it contains the minimum possible number of ones, and its transitive closure is equal to the transitive closure of matrix $$$a$$$.

Input

The first line of the input contains an integer $$$n$$$ ($$$1 \le n \le 100$$$).

Each of the next $$$n$$$ lines contains $$$n$$$ numbers 0 or 1 — the elements of matrix $$$a$$$.

Output

Output the required matrix $$$b$$$. If there are several correct answers, output any of them.

Example
Input
3
1 1 1
1 0 1
0 0 1
Output
0 1 0
1 0 1
0 0 1
Note

The matrices from the example have the following transitive closure: 

1 1 1
1 1 1
0 0 1