Hehezhou недавно приобрел остров $\alpha$ и планирует создать на нем систему управления.

Общая информация об острове $\alpha$:

• Остров $\alpha$ представляет собой прямоугольник размером $n$ строк на $m$ столбцов.
• Рельеф острова неоднороден. Если разделить остров на $n$ строк и $m$ столбцов, то высота участка в $i$-й строке и $j$-м столбце будет равна $h_{i,j}$.
• Высоты всех участков находятся в диапазоне $[1, n\times m]$, и все они различны.

Для эффективного управления островом $\alpha$ у Hehezhou возникла предварительная идея:

Когда Hehezhou стоит в определенной позиции, он может контролировать все участки в этой строке и в этом столбце.

Далее Hehezhou делит землю на $4$ части, как показано на рисунке:

На этом рисунке показано, что Hehezhou стоит в зеленой области и может контролировать все позиции в зеленой, синей и желтой областях.

Однако Hehezhou не может контролировать четыре области A, B, C и D. Поэтому он решает передать эти земли своим подчиненным, причем один подчиненный может получить только одну область. Его подчиненные также распределяют землю между своими подчиненными аналогичным образом... В частности, если какая-либо из областей A, B, C или D вырождается в пустую область, то эта область больше не распределяется.

У Hehezhou и его подчиненных есть свои предпочтения:

• Он может захотеть стоять в самой высокой точке, чтобы «сиять, как красное солнце».
• Он может захотеть стоять в самой низкой точке, чтобы «скрыться и стать королем теней».

То же самое касается подчиненных Hehezhou и их подчиненных. В частности, пусть Hehezhou будет подчиненным $0$-го уровня, подчиненный Hehezhou — подчиненным $1$-го уровня, подчиненный подчиненного Hehezhou — подчиненным $2$-го уровня и так далее. Дана последовательность $a$ длины $\min(n,m)$. Если человек является подчиненным $k$-го уровня:

• Если $a_k=0$, он встанет в самой низкой точке полученной им земли;
• Иначе, если $a_k=1$, он встанет в самой высокой точке полученной им земли.

«Брат моего брата — не мой брат». Люди, участвующие в управлении этой землей, признают только своего непосредственного начальника.

Hehezhou хочет знать, кто является начальником каждого человека, участвующего в управлении островом $\alpha$.

Выведите матрицу размером $n\times m$:

• Если в $i$-й строке и $j$-м столбце никто не стоит или там стоит сам Hehezhou, то элемент матрицы в $i$-й строке и $j$-м столбце равен $0$;
• В противном случае элемент матрицы в $i$-й строке и $j$-м столбце равен высоте позиции, на которой стоит начальник человека, находящегося в $i$-й строке и $j$-м столбце.

Входные данные

В первой строке два целых положительных числа $n, m$.

В следующей строке содержится $\min(n,m)$ чисел, где $i$-е число представляет $a_{i-1}$.

Далее следуют $n$ строк, в каждой из которых по $m$ целых положительных чисел, где $j$-е число в $i$-й строке обозначает $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$.

Объем входных и выходных данных в этой задаче довольно велик, рекомендуется использовать быстрые методы ввода-вывода.