时间限制： 2.0 秒

空间限制： 256 MB

问题描述

在图像编码的算法中，需要将一个给定的方形矩阵进行 Z 字形扫描 (Zigzag Scan)。给定一个 $n \times n$ 的矩阵，Z 字形扫描的过程如下图所示：

对于下面的 $4 \times 4$ 的矩阵，

1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

对其进行 Z 字形扫描后得到长度为 $16$ 的序列：

1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

请实现一个 Z 字形扫描的程序，给定一个 $n \times n$ 的矩阵，输出对这个矩阵进行 Z 字形扫描的结果。

输入格式

从标准输入读入数据。

输入的第一行包含一个整数 $n$，表示矩阵的大小。

输入的第二行到第 $n+1$ 行每行包含 $n$ 个正整数，由空格分隔，表示给定的矩阵。

输出格式

输出到标准输出。

输出一行，包含 $n \times n$ 个整数，由空格分隔，表示输入的矩阵经过 Z 字形扫描后的结果。

4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

评测用例规模与约定

$1 \le n \le 500$，矩阵元素为不超过 $1000$ 的正整数。