You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

小 Z 是一名刚入职的卫星图像工程师。

他所在的地面站每天都会收到一颗老卫星发回的灰度照片。照片太大，必须先切成一块块 n×n 的小方块，才能通过那条又窄又不稳定的信道传回地面。

奇怪的是，前辈们从来不让小 Z 按行发送数据。他们说：照片里相邻的像素往往长得几乎一样，真正"有信息量"的变化很少，而且大多挤 在方块的左上角；越往右下角走，数据就越细碎、越不重要。而这条信道说断就断，谁也说不准哪一秒会失联。

于是大家约定了一条"Z 字法则"：永远先把最重要的像素发出去。扫描路径从左上角出发，像 Z 字一样在方块里来回折返——沿对角线一条一条地向右下角推进，每走完一条就换一个方向。这样一来，哪怕信号在最糟的时刻断开，地面收 到的也一定是这张照片里最要紧的部分。

今天轮到小 Z 值班。他手上有一块 n×n 的像素块，请你帮他按这条法则，生成它的发送序列。

Description

在图像编码的算法中，需要将一个给定的方形矩阵进行 Z 字形扫描（Zigzag Scan），得到一个长度为 n×n 的序列。

Z 字形扫描从矩阵的左上角开始，沿着所有"右上—左下"方向的对角线依次读取，相邻两条对角线的读取方向相反：

• 第 1 条对角线：只有左上角 (1,1) 这一个格子；
• 第 2 条：从 (1,2) 读到 (2,1)；
• 第 3 条：从 (3,1) 读到 (1,3)；
• 第 4 条：从 (1,4) 读到 (4,1)；
• ……以此类推，直到读完全部 2n−1 条对角线。每个格子恰好被读到一次。

同一个格子 (i,j) 位于第 i+j−1 条对角线上；对角线的序号越大，位置越靠右下。

下图是一个 4×4 的方阵，格子里写的是该格子被读到的次序：

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

以样例中的矩阵为例，按对角线分组读出：

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

首尾相接，就得到长度为 16 的扫描序列。

Format

Input

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

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

数据范围：1 ≤ n ≤ 1000，矩阵中的每个数都在 1 到 1000 之间。

Output

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

Samples

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

Limitation

1s, 1024KiB for each test case.