题目描述

考虑四个满足

的整数。将它们按某种顺序放在一个正方形的四个顶点上，并依次连接

形成一个闭环。不同的顶点排列可能形成不同的几何形状，也可能形成相同的形状。

最终一共只可能得到三种环形，分别称为类型 $1$、类型 $2$ 和类型 $3$。

三种环形类型

矩阵及其各个 $2\times 2$ 子矩阵产生的环形示例如下：

矩阵环形示例

现在考虑一个 $n\times m$ 的矩阵，其中填入了 $1$ 到 $nm$ 的所有整数，并且每个整数恰好出现一次。

对于矩阵中的每个 $2\times 2$ 子矩阵，将其中四个数视为正方形四个顶点上的数，并按从小到大的顺序连接，便会得到上述三种环形之一。

你需要完成逆向构造：给定所有 $(n-1)(m-1)$ 个 $2\times 2$ 子矩阵对应的环形类型，构造一个满足要求的 $n\times m$ 矩阵。

输入格式

第一行包含两个整数 $n,m$（$2\le n,m\le 500$）。

接下来 $n-1$ 行，每行包含一个长度为 $m-1$ 的字符串，字符串中每个字符均为 1、2 或 3，表示对应 $2\times 2$ 子矩阵的环形类型。

输出格式

输出一个 $n\times m$ 的矩阵，矩阵中恰好包含 $1$ 到 $nm$ 的所有整数，且每个数出现一次，并使所有 $2\times 2$ 子矩阵产生的环形类型与输入一致。

可以证明答案一定存在。若有多种答案，输出任意一种。

样例

3 4
113
231

9 11 7 12
4 6 1 8
2 10 5 3