No testdata at current.

密码

时空限制

• CPU占用时长: 1秒
• 内存使用限制: 128MB

题目描述

小 $Y$ 发现了一个密码，这个密码的初始形式排列成了 $n \times n$ 的矩阵的形式。小Y需要首先按照蛇形矩阵的方式解读这个密码，如下图所示，从第一行第一个字符开始，第一步向右走，然后向左下方走到边界，接下去沿着边界走一步（可能向下可能向右），再向右上方走到边界，接下去沿着边界走一步（可能向下可能向右）……不断重复这个过程直到走到第 $n$ 行的第 $n$ 列停止。

（蛇形矩阵示意图：对角线Z字形遍历）

小 $Y$ 把走过路径的字符串起来，就得到了一个长度为 $n \times n$ 的字符串，如 "$THISISAVERYGOODPOEMITHINK$"，这是密码的中间形式，而小 $Y$ 需要把这个密码排列成最终形式，最终形式是把这个中间形式的密码按照螺旋矩阵的方式填入一个 $n \times n$ 的矩形中，如下图所示，从第一行第一个字符开始，第一步开始一直向右走直到碰到边界或是已有字符，再向下走到边界或已有字符，再向左走到边界或已有字符，再向上走到边界或已有字符……不断重复这个过程直到无路可走停止。

（螺旋矩阵示意图：顺时针螺旋填入）

每走一步就往当前位置中填入一个密码中间形式字符串中的字符，就得到了密码的最终形式。

现在给出密码的初始形式，小 $Y$ 想让你告诉他密码的最终形式。

输入格式

第一行 $1$ 个正整数 $n$，表示密码初始形式矩阵的大小。

第 $2 \ldots n+1$ 行每行 $n$ 个字符（字符都是大写字母）表示密码的初始形式。

输出格式

$n$ 行每行 $n$ 个大写字母表示密码的最终形式。

输入输出样例

样例 1

输入：

2
AB
CD

输出：

AB
DC

样例 2

输入：

4
ABCD
EFGH
IJKL
MNOP

输出：

ABEI
KHLF
NPOC
MJGD

样例 3

输入：

5
THSAD
IIVOP
SEOOH
RGETI
YMINK

输出：

THISI
POEMS
DNKIA
OIHTV
OGYRE

数据范围与提示

本题共有 $10$ 个测试点，每个测试点 $10$ 分。

• 对于测试点 1-3：$1 \le n \le 2$
• 对于测试点 4：保证矩阵中的所有字符完全相同
• 对于测试点 5-7：$1 \le n \le 5$
• 对于测试点 8-10：$1 \le n \le 500$