Grievous Lady

시간 제한1초메모리 제한1024 MB

요약

인접한 칸끼리 다른 색이 되도록 N×M 격자를 4가지 색으로 칠하되, 테두리에 미리 칠해진 칸을 지키고 아무 완성본이나 출력한다.

난이도: 보통10점 중 5점
유형: 그리디, 구현, 행렬, 완전 탐색
정답자: 아직 제출이 없습니다

문제

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.

예제1

예제 1

입력

2
5 5
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
7 7
1 0 0 2 0 0 3
0 0 0 0 0 0 0
0 0 0 0 0 0 0
4 0 0 0 0 0 4
0 0 0 0 0 0 0
0 0 0 0 0 0 0
3 0 0 2 0 0 1

예상 출력

1 2 1 2 1
2 1 2 1 2
1 2 1 2 1
2 1 2 1 2
1 2 1 2 1
1 2 1 2 1 2 3
2 1 2 1 2 3 1
1 2 1 2 1 4 2
4 1 2 1 2 1 4
1 2 1 2 1 2 1
2 3 2 1 2 1 2
3 1 3 2 1 2 1