Goal
Your program must output a solution to a Takuzu.
A Takuzu, also known as Binairo, is a logic puzzle involving placement of two symbols (0 and 1) on a square grid.
The objective is to fill the grid with 1s and 0s, constraints are :
- an equal number of 1s and 0s in each row and column
- no more than two of either number adjacent to each other
- no identical rows and no identical columns
Similar to Sudoku, each puzzle begins with several squares in the grid already filled. Each test has only one possible solution.
Input
Line 1 : an integer n, dimension of the square grid.
n lines : a string line with n digits corresponding to that line. A "." is used for an empty space.
Output
n lines : A string line with n digits corresponding to that line. The original numbers should not have changed, and there should be no "." left.
Constraints
0 < n <= 20
n is an even number
Example
Input
4
.1.0
..0.
.0..
11.0
Output
0110
1001
0011
1100
