题目背景

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

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

1.首先，你将沿着主对角线向右下方移动，每次尝试连续输出n个数字，从数字1开始，顺次填写完1到$n^2$的所有数字。

2.接下来，你的操作将全在与主对角线平行的矩阵斜线上，如果你在某条矩阵斜线上输出n哥数字，那么你就将顺着往下一个与主对角线平行的矩阵斜线去填充接下来的n哥数字，直到把矩阵填满。当然，你有时可能无法再一条斜线上完成连续输出n个数字，则按照以下规则。

3.当在某个矩阵斜线上无法一次性输出n个数字的话，如果此时处于矩阵的下三角形，你将会从上三角区域最右上角未填充数字的矩阵斜线开始进行填充数字，如果你此时处于矩阵的上三角区域，你将会从下三角区域最右上边未填充数字的矩阵斜线开始进行填充数字。

例如，在一个4*4的矩阵中，你最后输出的矩阵可能会像这样：

1 14 9 8

5 2 15 10

11 6 3 16

13 12 7 4

我们对于这个4*4的矩阵，首先填写1到4四个数字，填入主对角线上，恰好填满，接着顺着填充下一条与主对角线平行的矩阵斜线，需要一口气填入5到8四个数字，但是下一条矩阵斜线上只有3个数字可以填充，无法填充慢，因此根据规则往上三角区域的未填充数字的矩阵斜线进行填充，刚好填充完毕，接下来继续填充9到12四个数字，顺着填充结束的8所在的矩阵斜线的下一个矩阵斜线去填充，由于下一个矩阵斜线只有2个数字可以填充，然后更具规则往下半三角区域矩阵斜线进行填充，依此类推，最终填充完毕。

输入格式

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

输出格式

输出一个n*n的矩阵。

数据范围

对于25%的数据，$1\leq{n}\leq5$；

对于50%的数据，$1\leq{n}\leq10$

对于100%的数据，$1\leq{n}\leq20$

样例

4

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

2

1 4
3 2

3

1 7 6
4 2 8
9 5 3

Limitation

1000ms，524288K