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