题目描述

小明正在给一张方格地图填色。地图是一个 $n\times n$ 的方阵，每个方格中的数字为 $0$ 或 $1$。数字 $1$ 表示围栏，数字 $0$ 表示空地。

所有数字 $1$ 共同构成有且只有一条闭合围栏，不存在其他独立的围栏。围栏将空地分成围栏内和围栏外两部分。

从一个数字 $0$ 的方格出发，如果只经过数字 $0$ 的方格，能够向上、下、左、右移动到方阵边界上的某个方格，那么它位于围栏外；否则，它位于围栏内。

请将围栏内的所有数字 $0$ 改为 $2$。围栏上的数字 $1$ 和围栏外的数字 $0$ 保持不变。

输入格式

第一行包含一个整数 $n$，表示方阵的行数和列数。

接下来 $n$ 行，每行包含 $n$ 个由空格分隔的 $0$ 和 $1$，组成 $n \times n$ 的方阵。

保证方阵中有且只有一条由数字 $1$ 构成的闭合围栏，并且围栏内至少包含一个数字 $0$。

输出格式

输出填色后的完整方阵，每行的数字之间用一个空格分隔。

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

数据范围与提示

• $1 \leq n \leq 30$