CF1236C.Labs

In order to do some research, $n^2$ labs are built on different heights of a mountain. Let's enumerate them with integers from $1$ to $n^2$, such that the lab with the number $1$ is at the lowest place, the lab with the number $2$ is at the second-lowest place, $\ldots$, the lab with the number $n^2$ is at the highest place.

To transport water between the labs, pipes are built between every pair of labs. A pipe can transport at most one unit of water at a time from the lab with the number $u$ to the lab with the number $v$ if $u \gt v$.

Now the labs need to be divided into $n$ groups, each group should contain exactly $n$ labs. The labs from different groups can transport water to each other. The sum of units of water that can be sent from a group $A$ to a group $B$ is equal to the number of pairs of labs ($u, v$) such that the lab with the number $u$ is from the group $A$, the lab with the number $v$ is from the group $B$ and $u \gt v$. Let's denote this value as $f(A,B)$ (i.e. $f(A,B)$ is the sum of units of water that can be sent from a group $A$ to a group $B$).

For example, if $n=3$ and there are $3$ groups $X$, $Y$ and $Z$: $X = {1, 5, 6}, Y = {2, 4, 9}$ and $Z = {3, 7, 8}$. In this case, the values of $f$ are equal to:

• $f(X,Y)=4$ because of $5 \rightarrow 2$, $5 \rightarrow 4$, $6 \rightarrow 2$, $6 \rightarrow 4$,
• $f(X,Z)=2$ because of $5 \rightarrow 3$, $6 \rightarrow 3$,
• $f(Y,X)=5$ because of $2 \rightarrow 1$, $4 \rightarrow 1$, $9 \rightarrow 1$, $9 \rightarrow 5$, $9 \rightarrow 6$,
• $f(Y,Z)=4$ because of $4 \rightarrow 3$, $9 \rightarrow 3$, $9 \rightarrow 7$, $9 \rightarrow 8$,
• $f(Z,X)=7$ because of $3 \rightarrow 1$, $7 \rightarrow 1$, $7 \rightarrow 5$, $7 \rightarrow 6$, $8 \rightarrow 1$, $8 \rightarrow 5$, $8 \rightarrow 6$,
• $f(Z,Y)=5$ because of $3 \rightarrow 2$, $7 \rightarrow 2$, $7 \rightarrow 4$, $8 \rightarrow 2$, $8 \rightarrow 4$.

Please, divide labs into $n$ groups with size $n$, such that the value $\min f(A,B)$ over all possible pairs of groups $A$ and $B$ ($A \neq B$) is maximal.

In other words, divide labs into $n$ groups with size $n$, such that minimum number of the sum of units of water that can be transported from a group $A$ to a group $B$ for every pair of different groups $A$ and $B$ ($A \neq B$) as big as possible.

Note, that the example above doesn't demonstrate an optimal division, but it demonstrates how to calculate the values $f$ for some division.

If there are many optimal divisions, you can find any.

为了开展某项研究，共在一座山的不同高度上建造了 $n^2$ 个实验室。我们用 $1$ 到 $n^2$ 的整数对它们进行编号，其中编号为 $1$ 的实验室位于最低处，编号为 $2$ 的实验室位于第二低处，……，编号为 $n^2$ 的实验室位于最高处。

为了在各实验室之间输送水，任意两个实验室之间均铺设了一根管道。当且仅当 $u > v$ 时，一根管道才可将至多一单位的水从编号为 $u$ 的实验室输送到编号为 $v$ 的实验室。

现在需要将这些实验室划分为 $n$ 组，每组恰好包含 $n$ 个实验室。不同组之间的实验室可以相互输送水。从组 $A$ 向组 $B$ 可输送的水的总量，等于满足如下条件的实验室对 $(u, v)$ 的数量：编号为 $u$ 的实验室属于组 $A$，编号为 $v$ 的实验室属于组 $B$，且 $u > v$。我们将该值记为 $f(A,B)$（即 $f(A,B)$ 表示从组 $A$ 向组 $B$ 可输送的水的总量）。

例如，当 $n = 3$ 时，存在 $3$ 个组 $X$、$Y$ 和 $Z$：$X = \{1, 5, 6\}$，$Y = \{2, 4, 9\}$，$Z = \{3, 7, 8\}$。此时，各 $f$ 值如下：

• $f(X,Y)=4$，对应 $5 \rightarrow 2$、$5 \rightarrow 4$、$6 \rightarrow 2$、$6 \rightarrow 4$；
• $f(X,Z)=2$，对应 $5 \rightarrow 3$、$6 \rightarrow 3$；
• $f(Y,X)=5$，对应 $2 \rightarrow 1$、$4 \rightarrow 1$、$9 \rightarrow 1$、$9 \rightarrow 5$、$9 \rightarrow 6$；
• $f(Y,Z)=4$，对应 $4 \rightarrow 3$、$9 \rightarrow 3$、$9 \rightarrow 7$、$9 \rightarrow 8$；
• $f(Z,X)=7$，对应 $3 \rightarrow 1$、$7 \rightarrow 1$、$7 \rightarrow 5$、$7 \rightarrow 6$、$8 \rightarrow 1$、$8 \rightarrow 5$、$8 \rightarrow 6$；
• $f(Z,Y)=5$，对应 $3 \rightarrow 2$、$7 \rightarrow 2$、$7 \rightarrow 4$、$8 \rightarrow 2$、$8 \rightarrow 4$。

请将这 $n^2$ 个实验室划分为 $n$ 组，每组大小均为 $n$，使得所有可能的组对 $(A, B)$（其中 $A \neq B$）中 $f(A,B)$ 的最小值尽可能大。

换言之，将实验室划分为 $n$ 组，每组大小为 $n$，使得对任意两个不同组 $A$ 和 $B$（$A \neq B$），从 $A$ 向 $B$ 可输送的水的总量的最小值尽可能大。

注意：上述例子并未展示最优划分方式，而仅用于说明如何针对某一划分计算各 $f$ 值。

若存在多种最优划分方式，输出任意一种即可。

The only line contains one number $n$ ($2 \leq n \leq 300$).

唯一的一行包含一个数字 $n$（$2 \leq n \leq 300$）。

Output $n$ lines:

In the $i$-th line print $n$ numbers, the numbers of labs of the $i$-th group, in any order you want.

If there are multiple answers, that maximize the minimum number of the sum of units of water that can be transported from one group the another, you can print any.

输出 $n$ 行：

在第 $i$ 行中输出 $n$ 个数字，表示第 $i$ 组的实验室编号（顺序任意）。

若存在多个答案均能最大化“从一组到另一组可运输的水的单位总量”的最小值，则任选其一输出即可。

In the first test we can divide $9$ labs into groups ${2, 8, 5}, {9, 3, 4}, {7, 6, 1}$.

From the first group to the second group we can transport $4$ units of water ($8 \rightarrow 3, 8 \rightarrow 4, 5 \rightarrow 3, 5 \rightarrow 4$).

From the first group to the third group we can transport $5$ units of water ($2 \rightarrow 1, 8 \rightarrow 7, 8 \rightarrow 6, 8 \rightarrow 1, 5 \rightarrow 1$).

From the second group to the first group we can transport $5$ units of water ($9 \rightarrow 2, 9 \rightarrow 8, 9 \rightarrow 5, 3 \rightarrow 2, 4 \rightarrow 2$).

From the second group to the third group we can transport $5$ units of water ($9 \rightarrow 7, 9 \rightarrow 6, 9 \rightarrow 1, 3 \rightarrow 1, 4 \rightarrow 1$).

From the third group to the first group we can transport $4$ units of water ($7 \rightarrow 2, 7 \rightarrow 5, 6 \rightarrow 2, 6 \rightarrow 5$).

From the third group to the second group we can transport $4$ units of water ($7 \rightarrow 3, 7 \rightarrow 4, 6 \rightarrow 3, 6 \rightarrow 4$).

The minimal number of the sum of units of water, that can be transported from one group to another is equal to $4$. It can be proved, that it is impossible to make a better division.

在第一个测试用例中，我们可以将 $9$ 个实验室划分为三组：${2, 8, 5}$、${9, 3, 4}$、${7, 6, 1}$。

从第一组到第二组，可以运输 $4$ 单位的水（$8 \rightarrow 3$、$8 \rightarrow 4$、$5 \rightarrow 3$、$5 \rightarrow 4$）。

从第一组到第三组，可以运输 $5$ 单位的水（$2 \rightarrow 1$、$8 \rightarrow 7$、$8 \rightarrow 6$、$8 \rightarrow 1$、$5 \rightarrow 1$）。

从第二组到第一组，可以运输 $5$ 单位的水（$9 \rightarrow 2$、$9 \rightarrow 8$、$9 \rightarrow 5$、$3 \rightarrow 2$、$4 \rightarrow 2$）。

从第二组到第三组，可以运输 $5$ 单位的水（$9 \rightarrow 7$、$9 \rightarrow 6$、$9 \rightarrow 1$、$3 \rightarrow 1$、$4 \rightarrow 1$）。

从第三组到第一组，可以运输 $4$ 单位的水（$7 \rightarrow 2$、$7 \rightarrow 5$、$6 \rightarrow 2$、$6 \rightarrow 5$）。

从第三组到第二组，可以运输 $4$ 单位的水（$7 \rightarrow 3$、$7 \rightarrow 4$、$6 \rightarrow 3$、$6 \rightarrow 4$）。

各组之间可运输水量总和的最小值为 $4$。可以证明，不存在更优的分组方案。