Будем считать числа \(a\) и \(b\) соседними, если они отличаются ровно на единицу, то есть \(|a-b|=1\).
Будем считать клетки квадратной матрицы \(n \times n\) соседними, если они имеют общую сторону, то есть для клетки \((r, c)\) соседними являются клетки \((r, c-1)\), \((r, c+1)\), \((r-1, c)\) и \((r+1, c)\).
Для заданного числа \(n\) постройте квадратную матрицу \(n \times n\), такую что:
- Каждое число от \(1\) до \(n^2\) встречается в этой матрице ровно один раз;
- Если \((r_1, c_1)\) и \((r_2, c_2)\) соседние клетки, тогда числа записанные в них не должны быть соседними.
Выходные данные
Для каждого набора входных данных выведите:
- -1, если искомой матрицы не существует;
- искомую матрицу, иначе (любую подходящую, если таких существует много).
Матрицу следуют выводить в виде \(n\) строк, где каждая строка содержит \(n\) целых чисел.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
2
3
|
1
-1
2 9 7
4 6 3
1 8 5
|