You are given an $n \times n$ binary matrix where all of the values are missing except for the top & left edges. It is also guaranteed that the top left corner is a 1. Your task is to fill the missing values so that each column and each row has an even number of ones.

Input

The first line contains one integer: $n$
The following $n$ lines contain a string of length $n$.

Output

Print any valid way to fill the matrix. It is guaranteed that a solution always exists.

Constraints

• $2 \leq n \leq 100$
• The characters in the matrix are either 0, 1, or ?

Example

Input:

5
11000
0????
0????
0????
1????

Output:

11000
00000
01100
00101
10001