Grid Coloring

You are given a partially colored grid of size \(R \times C\) where each cell contains an integer from \(\{1,2,3,4\}\) representing a color, or \(0\) indicating an empty cell. Your task is to fill every empty cell in the grid with one of the colors \(1,2,3,4\) such that no two adjacent cells (sharing a common side) have the same color. All pre-colored cells must be preserved.

Constraints:

• You may assume that a solution always exists.
• Two cells are considered adjacent if they share an edge (vertically or horizontally).

Note: If a formula is included, it is rendered in \(\LaTeX\). For example, the set of allowed colors is \(\{1,2,3,4\}\).

inputFormat

The first line contains two integers (R) and (C), separated by a space. Each of the next (R) lines contains (C) integers separated by spaces, representing the grid. Here, (0) denotes an empty cell and (1,2,3,4) denote pre-colored cells.

outputFormat

Output the completed grid in the same format: (R) lines, each containing (C) integers separated by spaces. The grid must satisfy the condition that no two adjacent cells have the same color.## sample

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

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