考虑四个整数 $A, B, C, D$，满足 $A < B < C < D$。我们将它们按某种顺序放置在一个正方形的四个角上，并绘制一个回路 $A-B-C-D-A$。根据整数排列方式的不同，我们可以得到不同的回路形状，但某些排列会产生相同的形状：

我们可以得到三种可能的回路形状：

type 1 type 2 type 3

现在考虑一个 $n \times m$ 的矩阵，其中填入了 $1$ 到 $nm$ 的互不相同的整数。该矩阵中的每个 $2 \times 2$ 子矩阵都可以看作是一个四个角上带有整数的正方形。我们像之前一样为这些正方形中的每一个构建一个回路：

你的任务是执行逆运算。给定所有 $(n - 1)(m - 1)$ 个回路的形状类型，你需要构建一个 $n \times m$ 的矩阵，其中填入 $1$ 到 $nm$ 的互不相同的整数，使得其产生的回路形状与输入一致。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \leq n, m \leq 500$)。

接下来的 $n - 1$ 行，每行包含一个长度为 $m - 1$ 的字符串，不含空格。每个字符是一个 $1$ 到 $3$ 之间的数字，表示对应回路的形状类型。

输出格式

输出一个 $n \times m$ 的矩阵，其中填入 $1$ 到 $nm$ 的互不相同的整数，使得其产生的回路形状与输入一致。

可以证明这样的矩阵总是存在的。如果存在多个答案，输出其中任意一个即可。

样例

输入 1

3 4
113
231

输出 1

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