Hehezhou recently bought $\alpha$ Island and plans to establish a management system there.

The general situation of $\alpha$ Island is as follows:

• The shape of $\alpha$ Island is a rectangle with $n$ rows and $m$ columns.
• The terrain of $\alpha$ Island is uneven. Specifically, if the island is divided into $n$ rows and $m$ columns, the height of the land at row $i$ and column $j$ is $h_{i,j}$.
• The heights of all land plots are between $1$ and $n \times m$, and the height of each plot is unique.

To manage $\alpha$ Island effectively, Hehezhou has an initial idea:

When Hehezhou stands at a certain position, he can manage all the land in that row and that column.

Next, Hehezhou divides the land into $4$ parts, as shown in the figure:

This figure shows that when Hehezhou stands in the green area, he can manage all positions in the green, blue, and yellow areas.

However, Hehezhou cannot manage the four areas A, B, C, and D. Therefore, Hehezhou decides to assign these lands to his subordinates, where each subordinate can only receive one area. His subordinates will also distribute the land to their own subordinates in a similar way... Specifically, if any of the areas A, B, C, or D degenerate into an empty area, that degenerated area will no longer be assigned.

Hehezhou and his subordinates each have their own preferences:

• He might want to stand at the highest point, so he can be the "Red Sun" shining over everything.
• He might want to stand at the lowest point, so he can hide himself and become the "King of Stealth."

Hehezhou's subordinates and their subordinates are the same. Specifically, let Hehezhou be the $0$-th level subordinate of Hehezhou, Hehezhou's subordinate be the $1$-st level subordinate of Hehezhou, Hehezhou's subordinate's subordinate be the $2$-nd level subordinate of Hehezhou, and so on. Given a sequence $a$ of length $\min(n,m)$, if a person is the $k$-th level subordinate of Hehezhou:

• If $a_k=0$, he will stand at the lowest point of the land assigned to him;
• Otherwise, $a_k=1$, he will stand at the highest point of the land assigned to him.

"My boss's boss is not my boss." People involved in managing this land only recognize their direct boss.

Hehezhou wants to know who the boss is for every person involved in managing $\alpha$ Island.

Please output an $n \times m$ matrix:

• If no one is standing at row $i$ and column $j$, or if Hehezhou is standing there, the element at row $i$ and column $j$ of this matrix is $0$;
• Otherwise, the element at row $i$ and column $j$ of this matrix is the height of the position occupied by the boss of the person at row $i$ and column $j$.

Input

The first line contains two positive integers $n, m$.

The next line contains $\min(n,m)$ integers, where the $i$-th number represents $a_{i-1}$.

The next $n$ lines each contain $m$ positive integers, where the $j$-th number in the $i$-th line represents $h_{i,j}$.

Output

An $n \times m$ matrix representing the meaning as described in the problem.

Examples

Input 1

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

Output 1

0 0 0
0 9 0
0 0 1

Input 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

Output 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

Subtasks

Subtask $1$: $10$ points, $1 \leq n \times m \leq 10000$.

Subtask $2$: $10$ points, $1 \leq n \times m \leq 1000000$.

Subtask $3$: $10$ points, data is randomly generated: $a_i$ is randomly generated as $0$ or $1$, and the $h$ array is a random permutation.

Subtask $4$: $20$ points, guaranteed that $\forall i, a_i = 0$.

Subtask $5$: $30$ points, $1 \leq n \times m \leq 3000000$.

Subtask $6$: $20$ points, no special restrictions.

For $100\%$ of the data, $1 \leq n \times m \leq 4000000$.

The input and output volume for this problem is relatively large; it is recommended to use fast I/O methods.