Серёжа играл в змейку и почти успевал на поезд в ЛКШ. Но он не знал, что за последним уровнем последует дополнительный "бонусный".
Он представляет собой поле N×N, в каждой клетке которого лежит яблочко. Серёжина змея последовательно ползёт по диагоналям данного поля, поедая фрукты. Чтобы совершать такие поползновения, ей приходится после каждой диагонали менять направление движения (подробнее см. примеры).
Во входном файле одно целое число N (1 ≤ N ≤ 100).
Выведите ровно N строк по N чисел в каждой: для каждой клетки поля её номер в последовательности прохождения поля змеёй.