| Codeforces Round 632 (Div. 2) |
|---|
| Закончено |
Егор стремится набрать 1600 баллов на известном шахматном портале ChessForces и ему нужна ваша помощь!
Прежде чем приступить к решению проблемы, Егор хочет напомнить вам, как ходят шахматные фигуры. Шахматная ладья движется по прямым линиям вверх и вниз, влево и вправо на столько квадратов, сколько захочет. И когда она хочет, может остановиться. Ферзь ходит во всех направлениях по вертикали, горизонтали и по диагоналям на любом расстоянии. Вы можете увидеть примеры ниже.
Для достижения цели Егор должен исследовать следующую проблему:
Дана доска $$$N \times N$$$. Каждая ячейка доски имеет число от $$$1$$$ до $$$N ^ 2$$$, и все числа в клетках попарно различны.
В начале некоторая фигура ставится в ячейку с номером $$$1$$$. Заметьте, что эта ячейка уже считается посещенной. После этого каждый ход определяется следующим образом:
- Среди всех пока непосещенных клеток, которые могут быть достигнуты одним движением фигуры, фигура движется в ячейку с минимальным номером.
- Если все доступные ячейки уже посещены и на доске остались непосещенные клетки, то шахматная фигура телепортируется в непосещенную клетку с минимальным номером. В конце этого шага фигура вынуждена заплатить $$$1$$$ vun.
- Если все ячейки уже посещены, тогда процесс останавливается.
Егор должен найти такую нумерацию доски размера $$$N \times N$$$, что ладья, обойдя всю доску, заплатит строго меньше vun–ов, чем ферзь на этой доске. Помогите Егору найти подходящую доску размера $$$N \times N$$$, или скажите, что ее не существует.
Единственная строка содержит число $$$N$$$ — размер доски, $$$1\le N \le 500$$$.
Вывод должен содержать $$$N$$$ строк.
В $$$i$$$–ой строке выведите $$$N$$$ чисел — числа в $$$i$$$-м горизонтальном ряду доски. Все числа от $$$1$$$ до $$$N \times N$$$ должны быть использованы ровно один раз.
На вашей доске ладья должна платить строго меньше vun–ов, чем ферзь.
Если решения не существует, выведите $$$-1$$$.
Если существует более одного решения, выведите любое из них.
1
-1
4
4 3 6 12 7 5 9 15 14 1 11 10 13 8 16 2
В случае с доской размера $$$1 \times 1$$$, и ладья, и ферзь не платят ничего.
Во втором примере ладья проходит через клетки $$$1 \to 3 \to 4 \to 6 \to 9 \to 5 \to 7 \to 13 \to 2 \to 8 \to 16 \to 11 \to 10 \to 12 \to 15 \to \textbf{(1 vun)} \to 14$$$.
Ферзь проходит через $$$1 \to 3 \to 4 \to 2 \to 5 \to 6 \to 9 \to 7 \to 13 \to 8 \to 11 \to 10 \to 12 \to 15 \to \textbf{(1 vun)} \to 14 \to \textbf{(1 vun)} \to 16$$$.
В результате ладья платит 1 vun, а ферзь платит 2 vun.
