问题描述

在图像编码的算法中，需要将一个给定的方形矩阵进行 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

输入格式

第一行：一个整数 $n$，表示矩阵的大小。

接下来 $n$ 行，每行包含 $n$ 个正整数，表示给定的矩阵。

$(1 \leq n \leq 500)$，矩阵元素均为不超过 $1000$ 的正整数

输出格式

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

样例输入

3
1 2 3
4 5 6
7 8 9

样例输出

1 2 4 7 5 3 6 8 9