为了进行一些研究,$$$n^2$$$实验室建在山的不同高度上。让我们用从 $$$1$$$ 到 $$$n^2$$$ 的整数来枚举它们,这样编号为 $$$1$$$ 的实验室位于最低位置,编号为 $$$2$$$ 的实验室位于第二低位置,$$$\ldots$$$ 编号为 $$$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$$$ 大小的 $$$n$$$ 组,使得所有可能的组对 $$$A$$$ 和 $$$B$$$ ($$$A \neq B$$$) 上的值 $$$\min f(A,B)$$$ 最大。
换句话说,将实验室分为 $$$n$$$ 大小的 $$$n$$$ 组,使得每对不同的组 $$$A$$$ 和 $$$B$$$ ($$$A \neq B$$$) 可以从组 $$$A$$$ 运输到组 $$$B$$$ 的水单位总和的最小数量尽可能大。
请注意,上面的示例并未演示最佳除法,但它演示了如何计算某些除法的值 $$$f$$$。
如果有很多最佳划分,你可以找到任何一个。
输入
唯一一行包含一个数字 $$$n$$$ ($$$2 \leq n \leq 300$$$)。
输出
输出 $$$n$$$ 行:
在第 $$$i$$$ 行中打印 $$$n$$$ 数字,即第 $$$i$$$ 组的实验室编号,按照您想要的任何顺序。
如果有多个答案,可以最大化可以从一组传输到另一组的水单位总和的最小数量,您可以打印任何一个。
示例
输入 #1
3
输出 #1
2 8 5 9 3 4 7 6 1
注意
在第一个测试中,我们可以将 $$$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$$$。可以证明,不可能做出更好的划分。