我们称一个大小为 $N \times N$ 的矩阵 $A$ 是平衡的，如果对于所有 $1 \le i, j \le N - 1$，满足 $A[i][j] + A[i + 1][j + 1] = A[i + 1][j] + A[i][j + 1]$。

给定一个大小为 $N \times N$ 的矩阵 $A$。你的任务是输出另一个相同大小的矩阵 $B$，使得 $B$ 是平衡的，且对于所有 $1 \le i, j \le N$，满足 $B[i][j] \ge A[i][j]$。此外，你的矩阵 $B$ 中所有元素之和必须尽可能小。

输入格式

第一行包含一个整数 $N$，表示矩阵的行数和列数 ($1 \le N \le 50$)。 接下来的 $N$ 行，每行包含 $N$ 个整数。它们共同描述了矩阵 $A$。保证对于所有 $1 \le i, j \le N$，有 $0 \le A[i][j] \le 35\,000$。

输出格式

第一行输出你找到的平衡矩阵 $B$ 的元素之和。接下来的 $N$ 行，以与输入相同的格式输出该平衡矩阵。

任何满足题目所述约束的输出矩阵都将被接受。输出矩阵中的值没有任何限制（具体来说，它们可以超过 $35\,000$）。

样例

输入 1

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

输出 1

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