Hard choice

If you have some dilemma, then choose simply one (c) Alan

Alan relocates to the city where $n\times n$ buildings. All buildings can be represented as a grid with $n$ rows and $n$ columns. Some buildings in the city are special. Each day Alan will choose some building and he will get confused if there are two special buildings with equal distances to the chosen one. Distance calculated as the sum of absolute difference of rows and columns, i.e. distance from $(x_1,y_1)$ to $(x_2,y_2)$ is $|x_1-x_2|+|y_1-y_2|$.

For each building determine if Alan can live there without getting confused.

Input

The first line contains one integer $n(1\le n\le 1000)$ — the number of rows and columns. The next $n$ lines contain $n$ integers $a_{i,j}$ that equal to $1$ if building at the cell $(i,j)$ is special, and $0$ otherwise.

Output

Output $n$ lines, each with $n$ integers. Number equals to $1$ if Alan can live at the corresponding building without being confused, otherwise $0$.

Examples