Hehezhou niedawno kupił wyspę $\alpha$ i zamierza ustanowić na niej system zarządzania.

Sytuacja na wyspie $\alpha$ wygląda następująco:

• Wyspa $\alpha$ ma kształt prostokąta o wymiarach $n$ wierszy na $m$ kolumn.
• Ukształtowanie terenu wyspy jest nierówne. Dokładniej, jeśli podzielimy wyspę na $n$ wierszy i $m$ kolumn, wysokość działki w $i$-tym wierszu i $j$-tej kolumnie wynosi $h_{i,j}$.
• Wysokości wszystkich działek mieszczą się w przedziale $[1, n\times m]$ i każda działka ma unikalną wysokość.

Aby dobrze zarządzać wyspą $\alpha$, Hehezhou wpadł na wstępny pomysł:

Kiedy Hehezhou stoi w określonym miejscu, może zarządzać wszystkimi działkami w tym samym wierszu i tej samej kolumnie.

Następnie Hehezhou dzieli teren na $4$ obszary, jak pokazano na rysunku:

Ten rysunek pokazuje, że Hehezhou stojąc w zielonym obszarze, może zarządzać wszystkimi pozycjami w obszarach zielonym, niebieskim i żółtym.

Jednak Hehezhou nie może zarządzać czterema obszarami A, B, C i D. Dlatego Hehezhou postanawia przekazać te tereny swoim podwładnym, przy czym jeden podwładny może otrzymać tylko jeden obszar. Jego podwładni również będą dzielić teren między swoich podwładnych w podobny sposób... W szczególności, jeśli któryś z obszarów A, B, C lub D okaże się pusty, taki zdegradowany obszar nie jest dalej dzielony.

Hehezhou i jego podwładni mają swoje własne preferencje:

• Może chcieć stać w najwyższym punkcie, aby „promieniować światłem czerwonego słońca”.
• Może chcieć stać w najniższym punkcie, aby ukryć się jako „król cienia”.

Podwładni Hehezhou i ich podwładni mają podobne podejście. Dokładniej, niech Hehezhou będzie podwładnym stopnia $0$, podwładni Hehezhou będą podwładnymi stopnia $1$, podwładni podwładnych Hehezhou będą podwładnymi stopnia $2$, i tak dalej. Dany jest ciąg $a$ o długości $\min(n,m)$. Jeśli dana osoba jest podwładnym stopnia $k$:

• Jeśli $a_k=0$, stanie w najniższym punkcie przydzielonego mu terenu;
• W przeciwnym razie, jeśli $a_k=1$, stanie w najwyższym punkcie przydzielonego mu terenu.

„Brat mojego brata nie jest moim bratem”. Osoby zarządzające tym terenem uznają tylko swojego bezpośredniego przełożonego.

Hehezhou chce wiedzieć, kto jest przełożonym każdej osoby zarządzającej wyspą $\alpha$.

Wypisz macierz $n\times m$:

• Jeśli w $i$-tym wierszu i $j$-tej kolumnie nikt nie stoi lub stoi tam Hehezhou, element w $i$-tym wierszu i $j$-tej kolumnie macierzy wynosi $0$;
• W przeciwnym razie element w $i$-tym wierszu i $j$-tej kolumnie macierzy to wysokość miejsca zajmowanego przez przełożonego osoby stojącej w $i$-tym wierszu i $j$-tej kolumnie.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n, m$.

Kolejna linia zawiera $\min(n,m)$ liczb, gdzie $i$-ta liczba reprezentuje $a_{i-1}$.

Następnie $n$ linii, każda zawiera $m$ liczb całkowitych, gdzie $j$-ta liczba w $i$-tym wierszu oznacza $h_{i,j}$.

Wyjście

Macierz o wymiarach $n\times m$, zgodnie z opisem w treści zadania.

Przykład

Przykład 1

Wejście:

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

Wyjście:

0 0 0
0 9 0
0 0 1

Przykład 2

Wejście:

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

Wyjście:

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

Podzadania

Podzadanie $1$: $10$ punktów, $1\leq n\times m\leq 10000$.

Podzadanie $2$: $10$ punktów, $1\leq n\times m\leq 1000000$.

Podzadanie $3$: $10$ punktów, dane generowane losowo: $a_i$ losowane z $\{0, 1\}$, tablica $h$ jest losową permutacją.

Podzadanie $4$: $20$ punktów, gwarantowane $\forall i, a_i = 0$.

Podzadanie $5$: $30$ punktów, $1\leq n\times m \leq 3000000$.

Podzadanie $6$: $20$ punktów, brak dodatkowych ograniczeń.

Dla $100\%$ danych, $1\leq n\times m\leq 4000000$.

Ilość danych wejściowych i wyjściowych jest dość duża, zaleca się stosowanie szybkich metod wejścia/wyjścia.