CF178D1.Magic Squares

The Smart Beaver from ABBYY loves puzzles. One of his favorite puzzles is the magic square. He has recently had an idea to automate the solution of this puzzle. The Beaver decided to offer this challenge to the ABBYY Cup contestants.

The magic square is a matrix of size n × n. The elements of this matrix are integers. The sum of numbers in each row of the matrix is equal to some number s. The sum of numbers in each column of the matrix is also equal to s. In addition, the sum of the elements on the main diagonal is equal to s and the sum of elements on the secondary diagonal is equal to s. Examples of magic squares are given in the following figure:

Magic squares

You are given a set of _n_2 integers a__i. It is required to place these numbers into a square matrix of size n × n so that they form a magic square. Note that each number must occur in the matrix exactly the same number of times as it occurs in the original set.

It is guaranteed that a solution exists!

ABBYY 公司的聪明海狸酷爱解谜。他最钟爱的谜题之一便是“幻方”。最近，他萌生了一个想法：将这一谜题的求解过程自动化。于是，这只海狸决定将此挑战作为 ABBYY 杯编程竞赛的一道题目。

幻方是一个大小为 $n \times n$ 的矩阵，其元素均为整数。该矩阵每一行的元素之和均等于某个数 $s$；每一列的元素之和也均等于 $s$；此外，主对角线（从左上到右下）上所有元素之和等于 $s$，副对角线（从右上到左下）上所有元素之和也等于 $s$。如下图所示为若干幻方示例：

幻方

现给定一个包含 $n^2$ 个整数 $a_i$ 的集合。要求将这些数填入一个 $n \times n$ 的方阵中，使其构成一个幻方。注意：每个数在方阵中出现的次数必须与其在原始集合中出现的次数完全相同。

题目保证一定存在解！

The first input line contains a single integer n. The next line contains _n_2 integers a__i ( - 108 ≤ a__i ≤ 108), separated by single spaces.

The input limitations for getting 20 points are:

• 1 ≤ n ≤ 3

The input limitations for getting 50 points are:

• 1 ≤ n ≤ 4
• It is guaranteed that there are no more than 9 distinct numbers among a__i.

The input limitations for getting 100 points are:

• 1 ≤ n ≤ 4

第一行输入包含一个整数 $n$。下一行包含 $n^2$ 个整数 $a_i$（$-10^8 \leq a_i \leq 10^8$），以单个空格分隔。

获得 20 分的输入限制为：

• $1 \leq n \leq 3$

获得 50 分的输入限制为：

• $1 \leq n \leq 4$
• 保证在所有 $a_i$ 中至多有 9 个不同的数值。

获得 100 分的输入限制为：

• $1 \leq n \leq 4$

The first line of the output should contain a single integer s. In each of the following n lines print n integers, separated by spaces and describing the resulting magic square. In the resulting magic square the sums in the rows, columns and diagonals must be equal to s. If there are multiple solutions, you are allowed to print any of them.

输出的第一行应包含一个整数 $s$。接下来的 $n$ 行中，每行输出 $n$ 个整数，以空格分隔，描述所得到的幻方。在该幻方中，各行、各列以及两条主对角线的元素之和均必须等于 $s$。若存在多个解，输出其中任意一个即可。