题目描述

给定一个 $(n\times n)$ 的整数矩阵。将位于同一条$45^\circ$ 斜线（从左下到右上方向）的元素视为同一“行”。按如下“之”字形顺序遍历所有斜线：

1. 从第 1 条斜线开始（只含左上角单元），沿左下→右上方向输出；
2. 第 2 条斜线沿右上→左下方向输出；
3. 第 3 条斜线沿左下→右上方向输出；
4. 方向交替，直到遍历完所有 (2n-1) 条斜线。

请输出按上述规则得到的遍历序列。

例如：n = 3，3 × 3 的整数矩阵如下：

按照上述方式遍历矩阵的结果为：1、2、4、7、5、3、6、8、9。

输入格式

• 第一行输入整数 $n$。
• 接下来 $n$ 行，每行输入 $n$ 个整数，表示矩阵元素。

输出格式

输出一行，包含 $n\times n$ 个整数，为按题意遍历得到的序列，数与数之间以一个空格分隔。

样例输入输出

样例输入1

3
1 2 3
4 5 6
7 8 9

样例输出1

1 2 4 7 5 3 6 8 9

数据范围与测试点说明

• $3 \le n \le 100$；
• 矩阵元素为正整数，且 $1\le \text{元素}\le n^2$。

时间限制与内存限制

• 时间限制：1 秒
• 内存限制：1024 KiB