Problem B. Cross sum

Game Rules:

• Fill the empty cells with positive integers.
• In cells divided by a diagonal line, the number in the upper-right corner equals the XOR sum of the numbers in the contiguous empty cells immediately to its right, and the number in the lower-left corner equals the XOR sum of the numbers in the contiguous empty cells immediately below it.
• All integers filled into the empty cells must be distinct.

Apia gave Rimbaud a Kakuro puzzle. Being neither clever nor dexterous, Rimbaud cannot solve Kakuro at all, so she asks you to help her solve it. Since Rimbaud is very young, she can only perform operations on numbers not exceeding $2^{60} - 1$. Therefore, it is required that every number in the solution to the puzzle does not exceed $2^{60} - 1$.

Input

Each input contains multiple test cases. The first line contains an integer $T$ representing the number of test cases.

For each test case, the first line contains two positive integers $n$ and $m$, representing the number of rows and columns of the game, respectively.

The next $n$ lines each contain $m$ integers from $0$ to $4$, where the value at row $i$ and column $j$ represents the type of the cell at that position:

• $0$ means the cell is neither an empty cell nor a clue.
• $1$ means the cell contains a clue in the lower-left corner, and no clue in the upper-right corner.
• $2$ means the cell contains a clue in the upper-right corner, and no clue in the lower-left corner.
• $3$ means the cell contains clues in both the lower-left and upper-right corners.
• $4$ means the cell is an empty cell.

The input guarantees that the format represents a valid Kakuro puzzle, meaning every sequence of contiguous empty cells has a cell containing a clue to its left or above it.

The next $n$ lines each contain several non-negative integers, providing each clue in the puzzle in order from left to right. Specifically, if the cell type is $3$, the lower-left clue is given first, followed by the upper-right clue.

Output

For each test case, if a solution exists, output $n$ lines, each containing the numbers filled into the empty cells in order from left to right, such that the numbers in the empty cells are between $1$ and $2^{60} - 1$. Otherwise, output $-1$.

Examples

Input 1

3
3 3
0 1 1
2 4 4
2 4 4
3 7
2
6
3 3
0 1 1
2 4 4
2 4 4
1 1
1
1
2 2
0 1
2 4
0
0

Output 1

1 3
2 4
-1
-1

Constraints

• For $10\%$ of the data, $n, m \le 3$.
• For $30\%$ of the data, $n, m \le 15$.
• For $50\%$ of the data, $n, m \le 40$.
• For another $20\%$ of the data, only the first row and first column contain clues, and all other cells are empty.
• For $100\%$ of the data, $3 \le n, m \le 200$, $T \le 5$, and every number in the initial state does not exceed $2^{60} - 1$.

Figure 1. An example of a Kakuro puzzle grid.