题目描述

给定一个整数 $n$，你有 $n^2$ 个整数 $1, 2, \cdots, n^2$，你需要把他们填入一个 $n \times n$ 的矩阵中，每个格子恰好放一个整数； 换句话说，矩阵中的所有元素构成一个 $1 \sim n^2$ 的排列。

我们称两个格子是相邻的，当且仅当它们在同一行或同一列上相邻。

对于矩阵中的一个格子 $(i, j)$，记其元素为 $a_{i, j}$。 如果该格子所有相邻格子的元素都严格小于 $a_{i, j}$，或者都严格大于 $a_{i, j}$，那么我们称这个格子是一个极值点。

你的目标是构造一个矩阵，使得极值点的数量尽可能多。如果有多个矩阵满足条件，输出任意一个即可。

输入格式

输入包含一个整数 $n$ ($1 \leq n \leq 1000$) — 矩阵的大小。

输出格式

输出共 $n$ 行，每行 $n$ 个整数 $a_{i, j}$，代表你构造的矩阵。

样例

3

3 7 5
8 4 6
2 9 1