ABBYY 的智能海狸喜欢拼图。他最喜欢的谜题之一是幻方。他最近有了一个想法,可以自动化解决这个难题。海狸决定向 ABBYY 杯参赛者提出这一挑战。
幻方是一个大小为 n × n 的矩阵。该矩阵的元素是整数。矩阵每行中的数字之和等于某个数字 s。矩阵每列中的数字之和也等于 s。另外,主对角线上的元素之和等于s,次对角线上的元素之和等于s。下图给出了幻方的示例:
幻方
给你一组 n2 个整数 ai。需要将这些数字放入一个大小为 n × n 的方阵中,从而形成一个幻方。请注意,每个数字在矩阵中出现的次数必须与其在原始集合中出现的次数完全相同。
保证存在解决方案!
输入
第一个输入行包含单个整数 n。下一行包含 n2 个整数 ai ( - 108 ≤ ai ≤ 108),用单个空格分隔。
获得 20 点的输入限制为:
- 1 ≤ n ≤ 3
获得 50 点的输入限制为:
- 1 ≤ n ≤ 4
- 保证ai中不同的数字不超过9个。
获得 100 点的输入限制为:
- 1 ≤ n ≤ 4
输出
输出的第一行应包含单个整数 s。在接下来的 n 行中,每一行打印 n 个整数,用空格分隔并描述生成的幻方。在生成的幻方中,行、列和对角线的总和必须等于 s。如果有多个解决方案,您可以打印其中任何一个。
示例
输入 #1
3 1 2 3 4 5 6 7 8 9
输出 #1
15 2 7 6 9 5 1 4 3 8
输入 #2
3 1 0 -1 0 2 -1 -2 0 1
输出 #2
0 1 0 -1 -2 0 2 1 0 -1
输入 #3
2 5 5 5 5
输出 #3
10 5 5 5 5