B. Sphinx
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Once upon a time, a prison warden got lost in a forest during his adventure. Suddenly, a sphinx appeared in front of him, and said, "Lost human adventurer, proveth thy intellect by solving my riddle. Answer correctly, and I shall lead thee out this forest. Answer incorrectly, and I shall devour thee alive."

The sphinx's riddle was to adjust the "guiltiness values" of all the prisoners in the warden's prison to minimize the "chaoticness". It is known that:

  • The prisoners are arranged in a $$$n \times n$$$ matrix.
  • Each prisoner has a "guiltiness value", which is an integer.
  • Let $$$M$$$ be the matrix that represents to the guiltiness of all prisoners, i.e., $$$M_{i,j}$$$ is the guiltiness of the prisoner at the $$$i$$$-th row, $$$j$$$-th column. The "chaoticness" of the prison is defined as $$$\operatorname{rank} (M)$$$. Recall that $$$\operatorname{rank} (M)$$$ equals the dimension of the column space of $$$M$$$, or the maximum number of linear independent columns vectors of $$$M$$$.

The sphinx allows a series of operations to change the prisoners' guiltiness values. For each operation, the warden may choose any $$$2 \times 2$$$ submatrix of the prisoners, then apply one of the following to the four chosen prisoners:

  • Increase the guiltiness values of the prisoners at the top-left and bottom-right by 1, and decrease the guiltiness values of the prisoners at the top-right and bottom-left by 1.
  • Increase the guiltiness values of the prisoners at the top-right and bottom-left by 1, and decrease the guiltiness values of the prisoners at the top-left and bottom-right by 1.

Feared of being eaten alive, the warden asked you to write a program to solve the sphinx's riddle.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 2000$$$). Then $$$n$$$ lines follow, each containing $$$n$$$ integers. The $$$n \times n$$$ matrix formed by these numbers describe the initial guiltiness values of all prisoners. All values are integers with absolute values not exceeding $$$10^{9}$$$.

Output

Print the minimum possible chaoticness on the first line.

On the next $$$n$$$ lines, output a $$$n \times n$$$ matrix describing the guiltiness values of all prisoners after applying a series of some (possibly zero) operations. The rank of this matrix must correspond to the minimum chaoticness.

If there are multiple solutions to the riddle, output any one of them. Each value you output must have an absolute value of at most $$$10^{18}$$$ (it can be proven that this is always possible).

Scoring
  • Subtask 1 (17 points): $$$n = 2$$$
  • Subtask 2 (83 points): No additional constraints
Examples
Input
2
1 2
3 4
Output
2
0 3
4 3
Input
3
2 -1 -1
-2 -1 3
0 2 -2
Output
0
0 0 0 
0 0 0 
0 0 0