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