Egor 想要在著名的国际象棋门户 ChessForces 上获得 1600 分的评分,他需要你的帮助!
在你开始解决问题之前,叶戈尔想提醒你棋子是如何移动的。国际象棋车沿直线上下左右移动,想要走多少格就走多少格。当它想要的时候,它可以停下来。女王以任意距离向各个方向垂直和对角行走。您可以查看下面的示例。
为了实现目标,叶戈尔应该研究下一个主题:
有一个 $$$N \times N$$$ 板。棋盘上的每个单元格都有一个从 $$$1$$$ 到 $$$N ^ 2$$$ 的数字,并且所有单元格中的数字都是不同的。
一开始,一些国际象棋人物站在数字为$$$1$$$的单元格中。请注意,该单元格已被视为已访问。之后的每一步行动都由以下规则决定:
1. 在所有尚未访问过的单元格中,人物可以一次性到达的单元格中,它会进入数量最少的单元格。
2. 如果所有可访问的单元格都已被访问过,并且某些单元格尚未访问过,则人物将被传送到具有最小数量的未访问过的单元格。如果发生此步骤,该作品将支付 $$$1$$$ vun 的费用。
3. 如果所有单元都已被访问,则该过程停止。
Egor 应该找到一个 $$$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
输出 #1
-1
输入 #2
4
输出 #2
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$$$。
Queen经过$$$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。