34654번 - Grievous Lady 스페셜 저지다국어

You are given a grid of size $N \times M$. Your task is to color each cell of the grid with one of four colors: $1$, $2$, $3$, or $4$.

There is only one rule: any two adjacent cells must have different colors. Two cells are considered adjacent if they share a common edge.

Some cells in the grid may already be colored. These pre-colored cells are located only on the border of the grid. You must color all the remaining empty cells to create a complete grid that satisfies the rule.

The first line of the input contains a single integer $T$, the number of test cases.

The first line of each test case contains two integers $N$ and $M$.

The next $N$ lines describe the initial state of the grid. Each line contains $M$ space-separated integers. A value of $0$ represents an empty cell, while values from $1$ to $4$ represent a cell colored with that specific color.

For each test case, output $N$ lines representing the completed grid.

Each line should contain $M$ space-separated integers, where each integer is a color from $1$ to $4$.

If multiple solutions exist, you may print any one of them.

• $1 \le T \le 8\,000$
• $5 \le N, M \le 2 \cdot 10^5$
• The sum of $N \times M$ over all test cases does not exceed $2 \cdot 10^5$.
• In the initial grid, any non-zero cells are located only on the border (the first or last row, or the first or last column)
• It is guaranteed that a solution always exists for the given input.