方格填数

题目描述

给一个n\*n的方格矩阵,还有n\*n个整数,让你将这些整数填入矩阵,使得每行每列每个对角线上整数的和都相等。下面给出几个例子: 2 7 6 9 5 1 4 3 8 ![](https://cdn.luogu.com.cn/upload/pic/207.png)

输入输出格式

输入格式


输入格式 第一行一个整数n.(1<=n<=4) 第二行n\*n个整数 ai (-10^8<=ai<=10^8)

输出格式


输出格式 第一行一个整数s 代表每行每列每个对角线的和值 接下来输出一个n\*n的矩阵,表示填数方案。 数据保证有解,可能存在多种方案,输出字典序最小的(将每行顺次相连之后,字典序最小)

输入输出样例

输入样例 #1

3
1 2 3 4 5 6 7 8 9

输出样例 #1

15
2 7 6
9 5 1
4 3 8

说明

数据范围 80% 1<=n<=3 100%1<=n<=4