Умный Бобер из ABBYY очень любит различные головоломки. Одной из самых его любимых головоломок являются магические квадраты. Совсем недавно ему пришла в голову идея по автоматизации решения данной головоломки. Бобер решил обратиться с этой задачей к участникам ABBYY Cup'а.
Магический квадрат представляет собой матрицу размера n × n. Элементами этой матрицы являются целые числа. Сумма чисел в каждой из строк матрицы равна некоторому числу s. Сумма чисел в каждом из столбцов матрицы также равна числу s. Кроме этого, сумма элементов на главной диагонали равна s и сумма элементов на побочной диагонали равна s. Примеры магических квадратов приведены на следующем рисунке:
Магические квадраты Вам дан набор из n2 целых чисел ai. Требуется расположить эти числа в квадратной матрице размера n × n таким образом, чтобы они образовывали магический квадрат. Заметим, что каждое число должно встречаться в матрице ровно столько раз, сколько раз оно встречается в исходном наборе.
Гарантируется, что решение существует!
Выходные данные
Первая строка выходных данных должна содержать целое число s. В следующих n строках выведите по n целых чисел, разделенных пробелами и описывающих полученный магический квадрат. В выведенном магическом квадрате сумма в строках, столбцах и диагоналях должна быть равна s. Если решений несколько, разрешается выводить любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3 4 5 6 7 8 9
|
15
2 7 6
9 5 1
4 3 8
|
|
2
|
3
1 0 -1 0 2 -1 -2 0 1
|
0
1 0 -1
-2 0 2
1 0 -1
|
|
3
|
2
5 5 5 5
|
10
5 5
5 5
|