Hehezhou は最近 $\alpha$ 島を購入し、そこに管理体系を構築しようと計画している。
$\alpha$ 島の概要は以下の通りである。
- $\alpha$ 島の形状は $n$ 行 $m$ 列の長方形である。
- $\alpha$ 島の地勢は起伏に富んでいる。具体的には、島を $n$ 行 $m$ 列の区画に分割したとき、第 $i$ 行第 $j$ 列の区画の高さは $h_{i,j}$ である。
- すべての区画の高さは $[1, n\times m]$ の範囲にあり、各区画の高さは互いに異なる。
島を効率的に管理するため、Hehezhou は次のような初期案を立てた。
ある位置に立つと、その人はその行と列のすべての区画を管理できる。
次に、Hehezhou は土地を 4 つの領域に分割する。図は以下の通りである。
この図は、Hehezhou が緑色の領域に立った場合、緑色、青色、および黄色の領域のすべての位置を管理できることを示している。
しかし、Hehezhou は A、B、C、D の 4 つの領域を管理できない。そこで Hehezhou は、これらの土地を部下たちに分配することにした。1 人の部下は 1 つの領域のみを受け取ることができる。部下も同様の方法で、さらにその部下へと土地を分配していく。特に、A、B、C、D の領域が空になった場合、その領域は分配されない。
Hehezhou とその部下たちはそれぞれ異なる考えを持っている。
- 最高地点に立ち、太陽のように光を放ちたいと考える者。
- 最低地点に立ち、身を隠して王のように振る舞いたいと考える者。
Hehezhou の部下たちも同様である。具体的には、Hehezhou を 0 級部下、Hehezhou の部下を 1 級部下、その部下を 2 級部下、そのまた部下を 3 級部下……とする。長さ $\min(n,m)$ の数列 $a$ が与えられる。ある人が $k$ 級部下であるとき：
- $a_k=0$ ならば、その人は割り当てられた土地の最低点に立つ。
- $a_k=1$ ならば、その人は割り当てられた土地の最高点に立つ。
「私の上司の上司は私の上司ではない」。この土地の管理に関わる者は、自分の直属の上司のみを認識する。
Hehezhou は、$\alpha$ 島の管理に関わるすべての人の直属の上司が誰であるかを知りたいと考えている。
$n\times m$ の行列を出力せよ。
- 第 $i$ 行第 $j$ 列に誰も立っていない、あるいは Hehezhou が立っている場合、行列の第 $i$ 行第 $j$ 列の要素は $0$ とする。
- それ以外の場合、行列の第 $i$ 行第 $j$ 列の要素は、その位置に立っている人の直属の上司が立っている位置の高さとする。
入力
第一行に 2 つの正整数 $n, m$。
続く一行に $\min(n,m)$ 個の整数があり、第 $i$ 番目の数は $a_{i-1}$ を表す。
続く $n$ 行に、それぞれ $m$ 個の正整数があり、第 $i$ 行の第 $j$ 番目の数は $h_{i,j}$ を表す。
出力
問題の定義に従った $n$ 行 $m$ 列の行列を出力せよ。
入出力例
入力 1
3 3 0 1 0 1 2 3 4 5 6 7 8 9
出力 1
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
出力 2
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$ 点、すべての $i$ に対して $a_i = 0$ であることを保証する。
小課題 $5$：$30$ 点、$1\leq n\times m \leq 3000000$。
小課題 $6$：$20$ 点、特別な制限はない。
$100\%$ のデータに対して、$1\leq n\times m\leq 4000000$。
本題の入出力は非常に大きいため、高速な I/O 手法を使用することを推奨する。