Фаланга

[daniil123]

Великий полководец Сандро перед крупным сражением решил разработать боевое построение. В войске Сандро N^2 воинов, для каждого воина известна его сила - целое число от 1 до N^2. Силы всех воинов различны. После недолгих раздумий Сандро решил построить воинов в фалангу - N рядов по N воинов в каждом.
Во-первых, Сандро хочет сохранить жизни самых сильных воинов, поэтому, если воин не стоит в последнем ряду, то его сосед сзади должен быть сильнее его. Во-вторых, Сандро знает, что основные силы соперника сосредоточены на левом фланге атаки, поэтому если у воина есть сосед справа, то этот сосед должен быть сильнее его. Наконец, Сандро хочет скрыть истинную силу своего войска до начала сражения, поэтому сумма сил воинов, стоящих по периметру фаланги, должна быть минимально возможной.
В единственной строке записано натуральное число N(1<=N<=100).
Выведите план фаланги - N строк по N чисел в каждой. Строки должны соответствовать рядам фаланги. j-е число в i-й строке должно быть равно силе воина , стоящего j-м слева в i-м с начала ряде. Если возможных ответов несколько, выведите любой.
Пример:
Вход:
3
Выход:
1 2 4
3 6 8
5 7 9