#P1406. 方格填数

方格填数

题目描述

给一个 n×nn\times n 的方格矩阵,还有 n×nn\times n 个整数,让你将这些整数填入矩阵,使得每行每列每个对角线上整数的和都相等。下面给出几个例子:

输入格式

第一行一个整数 n (1n4)n\ (1 \le n \le 4)

第二行 n×nn\times n 个整数 ai (108ai108)a_i\ (-10^8 \le a_i \le 10^8)

输出格式

第一行一个整数 ss 代表每行每列每个对角线的和值。

接下来输出一个 n×nn\times n 的矩阵,表示填数方案。

数据保证有解,可能存在多种方案,输出字典序最小的(将每行顺次相连之后,字典序最小)

3
1 2 3 4 5 6 7 8 9

15
2 7 6
9 5 1
4 3 8


提示

数据范围及约定

  • 对于 80%80\% 的数据,保证 1n31 \le n \le 3
  • 对于 100%100\% 的数据,保证 1n41 \le n \le 4