eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Фаланга

Фаланга

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Великий полководец Сандро перед крупным сражением решил разработать боевое построение. В войске Сандро N^2 воинов, для каждого воина известна его сила — целое число от 1 до N^2. Силы всех воинов различны. После недолгих раздумий Сандро решил построить воинов в фалангу — N рядов по N воинов в каждом.

Во-первых, Сандро хочет сохранить жизни самых сильных воинов, поэтому если воин не стоит в последнем ряду, то его сосед сзади должен быть сильнее его. Во-вторых, Сандро знает, что основные силы соперника сосредоточены на левом фланге атаки, поэтому если у воина есть сосед справа, то этот сосед должен быть сильнее его. Наконец, Сандро хочет скрыть истинную силу своего войска до начала сражения, поэтому сумма сил воинов, стоящих по периметру фаланги, должна быть минимально возможной.

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

В единственной строке записано натуральное число N (1N100).

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

Выведите план фаланги — N строк по N чисел в каждой. Строки должны соответствовать рядам фаланги. j-е число в i-й строке должно быть равно силе воина, стоящего j-м слева в i-м с начала ряде. Если возможных ответов несколько, выведите любой.

Пример

Входные данные #1
3
Выходные данные #1
1 2 3
4 6 7
5 8 9