Description

There is an $n \times m \times 2$ chess box (surrounded by walls) and $nm$ black pieces and $nm$ red pieces. The pieces have several types. For each type, the number of red pieces equals the number of black pieces of that type. The type of a piece is marked by a characteristic value $v_{i,j}$. Pieces with the same characteristic value are of the same type, and pieces with different characteristic values are of different types.

The red pieces are placed on the lower layer of the chess box, and they have already been arranged. Now Vinsta wants to place the black pieces onto the upper layer of the chess box in a given order. Define the coordinates inside the box as: the top-left corner is $(1,1)$, the bottom-right corner is $(n,m)$, and the cell in row $i$ and column $j$ is $(i,j)$. Then each black piece placed must be put into a position that satisfies the following rules:

1. The position has no black piece, and directly below it there is a red piece of the same type as this black piece.

2. Under rule 1, if there are multiple positions, define the compactness of a position as the number of its four sides that are adjacent to a black piece or are a wall of the chess box. Choose the position with the maximum compactness.

3. Under rule 2, if there are still multiple positions, let the coordinate be $(i,j)$, and require $i+j$ to be minimum.

4. Under rule 3, if there are still multiple positions, require $i$ to be minimum.

Given the arrangement of the red pieces and the order in which the black pieces are inserted, please help her find, for each position, the insertion order of the black piece placed there.

Input Format

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

The next $n$ lines each contain $m$ integers. The integer in row $i$ and column $j$ is $v_{i,j}$.

The next line contains $nm$ integers, describing the type of the piece inserted each time, in order.

Output Format

Output $n$ lines each containing $m$ integers. For each position, the number $k_{i,j}$ means that the piece at $(i,j)$ is the $k_{i,j}$-th one inserted.

3 3
1 1 1
1 1 1
1 1 1
1 1 1 1 1 1 1 1 1

1 2 3
4 6 7
5 8 9

3 3
1 2 3
2 2 1
3 1 3
1 3 3 2 1 2 2 3 1

1 4 2
6 7 5
3 9 8

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

9 14 16 28 49 1 15 24 37 46
22 12 26 79 84 94 92 70 56 53
5 21 61 80 85 93 91 63 62 6
25 18 60 50 58 95 90 23 34 3
38 13 51 54 20 87 89 39 59 64
29 32 36 69 74 97 96 78 42 67
11 30 48 68 86 98 88 76 77 72
4 8 33 40 35 31 45 57 99 81
2 19 47 43 27 71 75 55 100 83
7 17 52 73 82 66 65 41 44 10

Hint

For $30\%$ of the testdata, $1 \le n, m \le 70$.

For another $30\%$ of the testdata, $v_{i,j} = 1$.

For $100\%$ of the testdata, $1 \le n, m \le 10^3$, $1 \le v_{i,j} \le 10$, and it is guaranteed that for each type, the numbers of black and red pieces are equal.

Translated by ChatGPT 5