Problem Description

Xiao Lan has recently been playing the $01$ game, a board game based on binary ideas. Specifically, the game is played on an $N \times N$ board. Each cell on the board must contain a digit $0$ or $1$. Initially, some cells already contain fixed digits, and the player is not allowed to change them. The player needs to fill in all other empty cells with digits so that the final board satisfies the following conditions:

1. All empty cells must be filled with a digit $0/1$.
2. In the horizontal or vertical direction, the same digit cannot appear consecutively more than twice.
3. In each row and each column, the number of $0$'s and $1$'s must be equal (for example, when $N = 4$, each row/column must contain $2$ zeros and $2$ ones).
4. Every row must be unique, so no row can be exactly the same as another row. Similarly, every column must be unique, so no column can be exactly the same as another column.

Now please solve the $01$ game together with Xiao Lan! The problem guarantees that every testdata has a unique answer.

Input Format

The first line contains an integer $N$, indicating the size of the board.

The next $N$ lines each contain $N$ characters. Each character is one of 0, 1, _ (ASCII codes are $48$, $49$, $95$ respectively). 0 means this cell is fixed as $0$, 1 means this cell is fixed as $1$, and _ means this is an empty cell to be filled by the player.

Output Format

Output $N$ lines, each containing $N$ characters, representing the solution. Each character can only be 0 or 1.

6
_0____
____01
__1__1
__1_0_
______
__1___

100110
010101
001011
101100
110010
011001

Hint

[Test Case Scale and Conventions]

For $60\%$ of the test cases, $2 \le N \le 6$.
For all test cases, $2 \le N \le 10$, and $N$ is even.

Thanks to @rui_er for providing the testdata.

Translated by ChatGPT 5