Rat in a Maze

Mô tả

Cho mê cung n×n với 1 là đường đi, 0 là tường. Chuột ở (0,0) cần đến (n-1,n-1). In đường đi hoặc "No path".

Input Format

Dòng 1: n.
n dòng sau: Ma trận n×n (0: tường, 1: đường).

Constraints

1 ≤ n ≤ 10

Sample Input

4
1 0 0 0
1 1 0 1
0 1 0 0
1 1 1 1

Sample Output

1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1