题目描述

喝喝粥 最近刚买下了 $\alpha$ 岛，他打算在这里建立一套管理体系。

$\alpha$ 岛的大致情况如下：

• $\alpha$ 岛的形状是一个 $n$ 行 $m$ 列的矩形。
• $\alpha$ 岛的地势高低不平，具体地，如果将岛屿的行平均划分成 $n$ 份，列平均划分成 $m$ 份，那么，第 $i$ 行第 $j$ 列的那一块地的高度就是 $h_{i,j}$ 。
• 所有地块的高度都在 $[1,n\times m]$ 之间，而且每一块地的高度互不相同。

为了很好地管理 $\alpha$ 岛，喝喝粥有了一个初步的想法：

当喝喝粥站在某一个位置时，他就可以管住这一行这一列的所有地。

接下来，喝喝粥将土地分成 $4$ 块，如图所示：

这张图表示喝喝粥站在绿色区域，可以管住绿色、蓝色和黄色区域的所有位置。

但是喝喝粥管不住 A、B、C、D 四个区域。于是喝喝粥就决定将这些土地分封给他的小弟们，一个小弟只能得到一个区域。它的小弟也会以类似的方式把土地分给它的小弟的小弟……特别地，如果 A、B、C、D 区域中有区域退化为空区域，那么这个退化的区域就不再被分封。

喝喝粥和它的小弟们各有各的想法：

• 他可能会想站在最高处，这样他就可以做红太阳光芒普照
• 他可能会想站在最低处，这样他就可以隐藏自己成为錈王

喝喝粥的小弟的小弟等人也是如此。具体地，设喝喝粥为喝喝粥的 $0$ 级小弟，喝喝粥的小弟为喝喝粥的 $1$ 级小弟，喝喝粥的小弟的小弟为喝喝粥的 $2$ 级小弟，喝喝粥的小弟的小弟的小弟为喝喝粥的 $3$级小弟……给定一个长度为 $\min(n,m)$ 的数列 $a$。那么，假设一个人是喝喝粥的 $k$ 级小弟：

• 如果 $a_k=0$ ，他会站在他分到的土地的最低点；
• 否则，$a_k=1$，他会站在他分到的土地的最高点。

“我的大哥的大哥不是我的大哥”。参与管理这片土地的人只认自己的大哥。

喝喝粥想知道每一个参与管理 $\alpha$ 岛的人的大哥是谁。

请你输出一个 $n\times m$ 的矩阵：

• 如果第 $i$ 行第 $j$ 列没有人站着或是喝喝粥站着，那么这个矩阵的第 $i$ 行第 $j$ 列的元素就是 $0$；
• 否则这个矩阵的第 $i$ 行第 $j$ 列的元素就是 第 $i$ 行第 $j$ 列的人的大哥所占位置的高度。

输入格式

第一行两个正整数 $n,m$。

接下来一行有 $\min(n,m)$ 个数，第 $i$ 个数代表 $a_{i-1}$ 。

接下来 $n$ 行，每行有 $m$ 个正整数，第 $i$ 行的第 $j$ 个数表示 $h_{i,j}$ 。

输出格式

一个 $n$ 行 $m$ 列的矩阵，表示的意义如题意所示。

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

0 0 0
0 9 0
0 0 1

12 8
1 0 0 1 0 1 0 1
87 19 88 4 25 38 1 69
74 81 15 22 89 65 94 23
8 85 70 40 26 92 79 24
61 76 73 63 39 28 84 35
18 37 54 13 64 52 44 51
6 29 42 86 11 32 5 3
36 34 82 9 59 43 67 12
30 27 93 56 49 20 14 50
55 80 83 33 7 31 41 91
75 2 48 10 17 21 45 78
53 71 57 46 68 96 77 66
72 58 16 47 60 95 90 62

0 0 0 2 0 0 96 0
0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 4 0 0 0 0 0
0 0 0 0 0 0 0 0
0 96 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 96 0 0 0 0 96

数据范围与提示

子任务 $1$：$10$ 分，$1\leq n\times m\leq 10000$。

子任务 $2$：$10$ 分，$1\leq n\times m\leq 1000000$。

子任务 $3$：$10$ 分，数据随机生成，生成方式为：$a_i$ 在 $0$ 和 $1$ 中随机生成, $h$ 数组为一个随机排列。

子任务 $4$：$20$ 分，保证 $\forall i,a_i = 0$。

子任务 $5$：$30$ 分，$1\leq n\times m \leq 3000000$。

子任务 $6$：$20$ 分，没有特殊限制。

对于 $100\%$ 的数据，$1\leq n\times m\leq 4000000$。

本题的输入和输出的量都比较大，建议使用较快的 IO 方式。