题目描述

研究员奈绪正在修补一张数值表。对于一个 $N\times N$ 的矩阵 $A$，如果对所有 $1\le i,j\le N-1$ 都有

则称 $A$ 是平衡矩阵。

现在给定一个 $N\times N$ 的矩阵 $A$。你需要输出另一个同样大小的矩阵 $B$，满足：

• $B$ 是平衡矩阵；
• 对所有 $1\le i,j\le N$，都有

• 在满足上述条件的所有矩阵中，$B$ 的所有元素之和尽可能小。

请输出任意一个满足要求且元素和最小的矩阵 $B$。

输入格式

第一行包含一个整数 $N$，表示矩阵的行数和列数。

接下来 $N$ 行，每行包含 $N$ 个整数，描述矩阵 $A$。

输出格式

第一行输出一个整数，表示你找到的平衡矩阵 $B$ 的元素和。

接下来 $N$ 行，每行输出 $N$ 个整数，表示矩阵 $B$。

只要输出矩阵满足题目要求即可被接受。输出矩阵中元素的大小没有额外限制，特别地，它们可以超过 $35000$。

数据范围

• $1\le N\le 50$；
• $0\le A[i][j]\le 35000$。

样例 1

输入

4
1 1 1 1
1 1 1 1
1 1 1 0
1 1 1 1

输出

16
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1