A aggressive man was locked up in top floor of MSIT building.

There are N^2 rooms in that floor all connected to each other in such a way that they form a square of side N.

Consider the top view of the building. The man is standing in top-left room. Since man is aggressive so he can break certain doors and enter the room.He can break doors which are labeled as 1 . The man wishes to move out of the building.

His friend informs him that there is a way out from bottom right room.Now man has to reach from his current position (top-left) to bottom-right(considering the top view of building). The doors labeled as 0 has police officers.

As a friend tell him the path that he should follow to get out without being notice by the police officers.

The man can move in following order - up,down,left,right.

Input format

Integer N Next N lines contains all the rooms of the top view of building. The rooms are denoted by 0 and 1 as required in the above problem. The man can move only in the rooms labeled as 1.

Output format

Print N^2 matrix in row major format showing all the possible paths that man should follow by 1 and rest elements of matrix should be 0. If more than 1 possible path exist , print them all in separate lines.

CONSTRAINTS

1 <= N <= 15