题目描述

数和游戏是一种棋盘填数游戏。棋盘上分为白色和灰色两种类型的格子。游戏目标是通过在白色的格子里填入数字 $1 \dots 9$ 来满足游戏要求。

游戏当中有一个称作“条目”的概念，条目指的就是在水平方向或者垂直方向上所有连续出现的白色格子的集合。具体来说从灰色格子右方（下方）相邻的白色格子出发，一直向右方（下方）行走直到走出棋盘边界或遇到灰色格子才停止，途中经过的所有的白色格子组成的集合就称为条目。例如上图中，我们用 $(x, y)$ 表示格子坐标，坐标 $(1, 4)$ 下方的条目就是由坐标 $(2, 4)$ 和 $(3, 4)$ 的白色格子构成的；坐标 $(5, 1)$ 右方的条目是由坐标 $(5, 2)$、$(5, 3)$ 的白色格子构成的。但注意坐标 $(7, 2)$、$(7, 3)$、$(7, 4)$ 处的格子的集合并不是一个条目，在加入坐标 $(7, 5)$ 的格子后才是一个条目。

游戏具体要求如下：游戏在一个 $M \times N$ 大小的格子棋盘上进行，其中格子分为白色和灰色两种类型：

1. 白色格子，此种类型的格子应当填入一个 $1 \dots 9$ 范围内的整数并满足所有灰色格子的要求；
2. 灰色格子，此种类型的格子用一条对角线将格子分为了左下（用 $A$ 表示）和右上（用 $B$ 表示）两部分，若 $A$ 中有数字，则表示 $A$ 所在的格子下方条目中的数字之和应该等于 $A$ 中的数字；若 $B$ 中有数字，则表示 $B$ 所在的格子右方条目中的数字之和应该等于 $B$ 中的数字。除此之外还有一个重要的约束条件：每一个条目中不能出现重复的数字，即在每一个条目之中，$1 \dots 9$ 中的每个数字最多只能出现一次。我们保证游戏一定有一个唯一解。

上图是一个数和游戏的例子示意图，坐标 $(1, 4)$ 处是一个灰色格子，它的 $A$ 中的数字为 $4$，这意味它下方的条目（即坐标 $(2, 4)$、$(3, 4)$ 处的白色格子）中的数字之和应该为 $4$；坐标 $(5, 1)$ 处是一个灰色格子，它的 $B$ 中的数字是 $16$，这表示它右方的条目（即坐标 $(5, 2)$、$(5, 3)$ 处的白色格子）中的数字之和应该为 $16$。

输入格式

第一行输入两个正整数 $M$、$N$ 分别用来表示棋盘的宽度和高度。

接下来 $M$ 行，每行输入 $N$ 个格子的信息。对于白色格子，只需要输入一个整数 $1$；对于灰色格子，首先输入一个整数 $2$，接下来再输入两个正整数分别表示灰色格子中 $A$ 中的数字和 $B$ 中的数字，如果是 $-1$ 则表示 $A$ 或 $B$ 中没有数字。其中每一行输入的所有的相邻整数之间均用空格隔开。

输出格式

输出 $M$ 行，每行包含 $N$ 个格子的信息，如果当前位置是一个灰色格子则用一个 _ 符号来表示；如果是一个白色格子，则用一个 $1 \dots 9$ 之间的整数来表示将要填入当前白色格子内的数字。每一行中，相邻格子之间的输出用一个空格分隔。

7 7
2 -1 -1 2 -1 -1 2 -1 -1 2 4 -1 2 14 -1 2 19 -1 2 11 -1
2 -1 -1 2 -1 -1 2 21 24 1 1 1 1
2 -1 -1 2 26 18 1 1 1 1 1
2 -1 12 1 1 2 -1 -1 2 -1 3 1 1
2 -1 16 1 1 2 17 -1 2 11 8 1 1
2 -1 28 1 1 1 1 1 2 -1 -1
2 -1 14 1 1 1 1 2 -1 -1 2 -1 -1

_ _ _ _ _ _ _
_ _ _ 3 9 7 5
_ _ 6 1 5 4 2
_ 8 4 _ _ 2 1
_ 9 7 _ _ 5 3
_ 7 3 9 8 1 _
_ 2 1 8 3 _ _

提示

样例说明

此局游戏的答案如上图所示。

评测用例规模与约定

• 对于 $30\%$ 的测试用例，$3 \leq M, N \leq 5$。
• 对于 $60\%$ 的测试用例，$3 \leq M, N \leq 10$。
• 对于 $100\%$ 的测试用例，$3 \leq M, N \leq 15$，$1 \leq$ 灰色格子中的数字 $\leq 50$。