D2. Магические квадраты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Умный Бобер из ABBYY очень любит различные головоломки. Одной из самых его любимых головоломок являются магические квадраты. Совсем недавно ему пришла в голову идея по автоматизации решения данной головоломки. Бобер решил обратиться с этой задачей к участникам ABBYY Cup'а.

Магический квадрат представляет собой матрицу размера n × n. Элементами этой матрицы являются целые числа. Сумма чисел в каждой из строк матрицы равна некоторому числу s. Сумма чисел в каждом из столбцов матрицы также равна числу s. Кроме этого, сумма элементов на главной диагонали равна s и сумма элементов на побочной диагонали равна s. Примеры магических квадратов приведены на следующем рисунке:

Магические квадраты

Вам дан набор из n2 целых чисел ai. Требуется расположить эти числа в квадратной матрице размера n × n таким образом, чтобы они образовывали магический квадрат. Заметим, что каждое число должно встречаться в матрице ровно столько раз, сколько раз оно встречается в исходном наборе.

Гарантируется, что решение существует!

Входные данные

Первая строка входных данных содержит единственное целое число n. Следующая строка содержит n2 целых чисел ai ( - 108 ≤ ai ≤ 108), разделенных единичными пробелами.

Ограничения на входные данные для получения 20 баллов:

  • 1 ≤ n ≤ 3

Ограничения на входные данные для получения 50 баллов:

  • 1 ≤ n ≤ 4
  • Гарантируется, что среди ai не более 9 различных чисел.

Ограничения на входные данные для получения 100 баллов:

  • 1 ≤ n ≤ 4
Выходные данные

Первая строка выходных данных должна содержать целое число s. В следующих n строках выведите по n целых чисел, разделенных пробелами и описывающих полученный магический квадрат. В выведенном магическом квадрате сумма в строках, столбцах и диагоналях должна быть равна s. Если решений несколько, разрешается выводить любое.

Примеры
Входные данные
3
1 2 3 4 5 6 7 8 9
Выходные данные
15
2 7 6
9 5 1
4 3 8
Входные данные
3
1 0 -1 0 2 -1 -2 0 1
Выходные данные
0
1 0 -1
-2 0 2
1 0 -1
Входные данные
2
5 5 5 5
Выходные данные
10
5 5
5 5