题目描述

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

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

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

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

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

接下来，喝喝粥将土地分成 $4$ 块，如图所示:https://s1.ax1x.com/2020/10/29/BGltRs.png

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

但是喝喝粥管不住 $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 \times m$ 的矩阵，表示的意义如题意所示。

样例 1

输入： $3$ $3$ $0$ $1$ $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$

输出： $0$ $0$ $0$ $0$ $9$ $0$ $0$ $0$ $1$

样例 2

输入： $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 方式。