Description

Given an $n \times n$ grid and $n \times n$ integers, fill these integers into the grid so that the sum of the integers in every row, every column, and each diagonal are all equal. Several examples are shown below.

Input Format

The first line contains an integer $n\ (1 \le n \le 4)$.

The second line contains $n \times n$ integers $a_i\ (-10^8 \le a_i \le 10^8)$.

Output Format

Output an integer $s$ on the first line, representing the common sum of every row, every column, and each diagonal.

Then output an $n \times n$ matrix, representing a valid filling scheme.

The testdata guarantees that there is a solution. There may be multiple solutions; output the lexicographically smallest one (after concatenating the rows in order).

3
1 2 3 4 5 6 7 8 9

15
2 7 6
9 5 1
4 3 8

Hint

Constraints and Conventions

• For $80\%$ of the testdata, it is guaranteed that $1 \le n \le 3$.
• For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 4$.

Translated by ChatGPT 5