In some one-on-one games (such as chess, table tennis, or badminton singles), we often encounter the interesting situation where A beats B, B beats C, and C beats A. We can figuratively call this a "Rock-Paper-Scissors" situation. Sometimes, people enjoy counting how many such "Rock-Paper-Scissors" situations occur, i.e., how many unordered triples $(A, B, C)$ exist such that one person in the triple beats another, that person beats the third, and the third beats the first. Note that "unordered" means the order of elements in the triple does not matter; $(A, B, C)$, $(A, C, B)$, $(B, A, C)$, $(B, C, A)$, $(C, A, B)$, and $(C, B, A)$ are considered the same situation.

There are $N$ people participating in a tournament where every pair of people must play exactly one game, for a total of $\frac{N(N-1)}{2}$ games. Some games have already been played. We want to know the maximum number of "Rock-Paper-Scissors" situations that can occur after all games are finished in the extreme case. That is, given the results of the games already played, you can arrange the results of the remaining games to maximize the number of "Rock-Paper-Scissors" situations.

Input

The first line of the input contains an integer $N$, representing the number of participants.

This is followed by an $N \times N$ matrix of numbers: there are $N$ lines in total, each containing $N$ numbers separated by spaces.

If the number in the $j$-th column of the $(i+1)$-th row is $1$, it means $i$ has already beaten $j$; if the number is $0$, it means $i$ lost to $j$; if the number is $2$, it means the game between $i$ and $j$ has not yet taken place. The numbers on the diagonal of the matrix (i.e., the $(i+1)$-th row and $i$-th column) are all $0$, which are merely placeholders and have no significance.

The input is guaranteed to be valid and consistent. For $i \neq j$, the two numbers at the $(i+1)$-th row, $j$-th column and the $(j+1)$-th row, $i$-th column are either both $2$, or one is $0$ and the other is $1$.

Output

The first line of the output contains an integer representing the maximum number of "Rock-Paper-Scissors" situations in your arranged tournament results.

Starting from the second line of the output, provide an $N \times N$ matrix of numbers in the same format as the input. The number in the $j$-th column of the $(i+1)$-th row describes the result of the game between $i$ and $j$, where $1$ means $i$ beat $j$, and $0$ means $i$ lost to $j$. Unlike the input matrix, this matrix must not contain the number $2$ representing unplayed games. The numbers on the diagonal must be $0$. The output matrix must be valid and consistent.

Constraints

$30\%$ of the data: $N \le 6$ $100\%$ of the data: $N \le 100$

Examples

Input 1

3
0 1 2
0 0 2
2 2 0

Output 1

1
0 1 0
0 0 1
1 0 0

Note

For each test case, you will receive full marks only if the first line of your program's output matches the standard answer and you provide a valid corresponding arrangement; otherwise, you will receive 0 points for that test case.