龙与高桥

题目描述

有一个 $N$ 行 $N$ 列的网格,其中 $N$ 是不超过 $45$ 的奇数。

从上数第 $i$ 行、从左数第 $j$ 列的格子记为 $(i,j)$。

在这个网格中,需要按以下条件配置高桥君和一条由编号 $1$ 到 $N^2-1$ 的 $N^2-1$ 个部件组成的龙。

• 高桥君必须配置在网格的中央,即格子 $(\frac{N+1}{2},\frac{N+1}{2})$。
• 除高桥君所在的格子外,每个格子必须恰好配置一个龙部件。
• 对于所有满足 $2 \leq x \leq N^2-1$ 的整数 $x$,龙部件 $x$ 必须配置在与部件 $x-1$ 所在格子边相邻的格子中。
• 格子 $(i,j)$ 与格子 $(k,l)$ 边相邻,当且仅当 $|i-k|+|j-l|=1$。

输出一个满足条件的配置方法。保证存在满足条件的配置。

输入格式

输入按以下格式从标准输入给出。

$N$

输出格式

输出 $N$ 行。

将格子 $(i,j)$ 配置高桥君时记为 T、配置部件 $x$ 时记为 $x$,在第 $i$ 行输出 $X_{i,1},\ldots,X_{i,N}$,以空格分隔。

样例

5

1 2 3 4 5
16 17 18 19 6
15 24 T 20 7
14 23 22 21 8
13 12 11 10 9

数据范围

• $3 \leq N \leq 45$
• $N$ 是奇数

提示

除此之外,以下输出也满足所有条件,因此也是正确答案。

9 10 11 14 15
8 7 12 13 16
5 6 T 18 17
4 3 24 19 20 
1 2 23 22 21

另一方面,以下输出分别是不正确的。

高桥君不在中央。

1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 T

部件 $23$ 和部件 $24$ 所在的格子没有边相邻。

1 2 3 4 5
10 9 8 7 6
11 12 24 22 23
14 13 T 21 20
15 16 17 18 19

答案不唯一,输出任意合法解即可。