P1406 Fill Numbers in a Grid

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. 

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 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).

### 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