多格骨牌（polyomino）是由一个或多个单位正方形边对边连接而成的平面几何图形。下图展示了两个多格骨牌的例子。多格骨牌中包含的每个正方形称为一个单元格，两个共享一条边的单元格互为邻居。注意，一个单元格的邻居数量可以是 0、1、2、3 或 4。如果多格骨牌 $P$ 中每一对单元格 $(a, b)$ 都存在一条由相邻单元格组成的路径连接 $a$ 和 $b$，则称 $P$ 是连通的；如果 $P$ 是连通的且不包含任何“孔洞”，则称 $P$ 是单连通的。在下图中，左侧的图形是单连通的，而右侧的不是。我们将处理一种单连通多格骨牌 $P$，使得 $P$ 中包含的每个单元格都有两个或更多的邻居。

多格骨牌 $P$ 的平铺是指用 $D1$、$D2$、$T1$ 和 $T2$ 的平移副本对 $P$ 进行镶嵌（覆盖，且无重叠、无空隙），其中 $D1$（或 $D2$）是由两个单位正方形水平（或垂直）连接而成的多格骨牌，$T1$（或 $T2$）是由三个单位正方形水平（或垂直）连接而成的多格骨牌。下图展示了 $D1$、$D2$、$T1$ 和 $T2$。根据 $P$ 的形状，其平铺可能存在，也可能不存在。

为了表示多格骨牌 $P$，我们假设 $P$ 包含在一个 $n \times n$ 的单位正方形网格中。我们将网格中的每个单位正方形 $s$ 标记为 1（如果 $s$ 是 $P$ 的单元格）或 0（否则）。那么，包含 $P$ 的单位正方形网格可以用一个 $n \times n$ 的 0 和 1 矩阵来表示。$P$ 的平铺也可以用一个 $n \times n$ 的整数矩阵来表示，如下所示：如果 $P$ 的一个单元格被 $D1$ 或 $D2$ 的副本覆盖，则我们将该单元格分别标记为 2 或 3。如果 $P$ 的一个单元格被 $T1$ 或 $T2$ 覆盖，则我们将该单元格分别标记为 4 或 5。下图展示了一个平铺及其表示的例子。

给定一个由 $n \times n$ 的 0 和 1 矩阵表示的单连通多格骨牌 $P$（其中 $P$ 中每个单元格都有两个或更多邻居），编写一个程序，输出 $P$ 的一种平铺方式（如果存在）。

输入格式

程序从标准输入读取数据。输入的第一行包含一个整数 $2 \le n \le 1,000$，其中 $n$ 是包含多格骨牌 $P$ 的单位正方形网格的行数和列数。接下来的 $n$ 行，每行包含 $n$ 个 0 或 1，其中 1 表示该正方形是 $P$ 的单元格。多格骨牌 $P$ 是单连通的，且 $P$ 中包含的每个单元格都有两个或更多的邻居。

输出格式

程序将结果写入标准输出。如果存在 $P$ 的平铺，则使用 $n$ 行打印 $P$ 的平铺结果。每行包含 $n$ 个 0 到 5 之间的整数。0 表示该正方形不是 $P$ 的单元格。2 表示该正方形是 $P$ 的单元格，且被 $D1$ 覆盖。类似地，3、4 或 5 分别表示该正方形是 $P$ 的单元格，且被 $D2$、$T1$ 或 $T2$ 覆盖。如果不存在可能的平铺，则输出 -1。

样例

样例输入 1

3
011
111
111

样例输出 1

022
322
322

样例输入 2

6
011111
011111
011100
001000
111111
111111

样例输出 2

053533
053533
053500
003000
222222
444444