1947：矩阵寻宝之旅

在蒜头王国的智慧宫殿里，蒜头君发现了一张古老而神秘的藏宝图，这张藏宝图被巧妙地隐藏在一个特殊的矩阵之中。为了找到隐藏的宝藏，蒜头君需要按照一种独特的路径揭示矩阵中的秘密数字。现在，他需要你的智慧和帮助！

想象你站在一个神奇的矩阵迷宫入口，这个矩阵共有 $n$ 行 $n$ 列 $(n\le 20)$，里面藏有指引至宝藏的关键数字。你的任务是从矩阵的左上角 $(1,1)$ 位置出发，按照特定的路线输出数字。具体来说：

• 首先，你将沿着主对角线向右下方移动，每次尝试连续输出 $n$ 个数字，从数字 $1$ 开始，顺次填写完 $1$ 到 $n^2$ 的所有数字。
• 接下来，你的操作将全在主对角线平行的矩阵斜线上，如果你在某条矩阵斜线上完成输出 $n$ 个数字，那么你就将顺着往下一个与主对角线平行的矩阵斜线去填充接下来的 $n$ 个数字，直到把矩阵填满。当然，你有时可能无法在一条斜线上完成连续输出 $n$ 个数字，则按下面规则。
• 当在某个矩阵斜线上无法一次输出 $n$ 个数字的话，如果你此时处于矩阵的下三角区域，你将会从上三角区域最右上角未填充数字的矩阵斜线开始进行填充数字，，如果你此时处于矩阵的上三角区域，你将会从下三角区域最左上边未填充数字的矩阵斜线开始进行填充数字。

输入为一行包含一个整数 $n$

$1\le n\le 20$

4

1 14 9 8
5 2 15 10
11 6 3 16
13 12 7 4

3

1 7 6
4 2 8
9 5 3