You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Diverta City

题目描述

构造一张 $n$ 个点的无向完全图,使得所有的 $\frac{n!}{2}$ 条哈密顿路径的边权和互不相同。要求所有边权都是正数,且任意哈密顿路径的边权和不超过 $10^{11}$。

输入格式

输入格式如下，一行一个正整数 $N$ 。

$N$

输出格式

输出格式如下，输出这个无向完全图的邻接矩阵。

$w_{1,\ 1}\ w_{1,\ 2}\ w_{1,\ 3}\ ...\ w_{1,\ N}$ $w_{2,\ 1}\ w_{2,\ 2}\ w_{2,\ 3}\ ...\ w_{2,\ N}$ : : : $w_{N,\ 1}\ w_{N,\ 2}\ w_{N,\ 3}\ ...\ w_{N,\ N}$

这里$w_{i,\ j}$ 是 $i$ 到 $j$ 的边的长度。

邻接矩阵显然需要满足以下性质：

• $w_{i,\ i}\ =\ 0$
• $w_{i,\ j}\ =\ w_{j,\ i}\ (i\ \neq\ j)$
• $1\ \leq\ w_{i,\ j}\ \leq\ 10^{11}\ (i\ \neq\ j)$

目的を達成する道路の長さの組み合わせが複数存在する場合は、そのうちのどれを出力しても正解となる。

样例 #1

样例输入 #1

3

样例输出 #1

0 6 15
6 0 21
15 21 0

样例 #2

样例输入 #2

4

样例输出 #2

0 111 157 193
111 0 224 239
157 224 0 258
193 239 258 0

提示

数据范围

• $2 \leq n \leq 10$

样例解释 1

所有哈密顿路径的权值如下：

• $1\ →\ 2\ →\ 3$: $6\ +\ 21\ =\ 27$
• $1\ →\ 3\ →\ 2$: $15\ +\ 21\ =\ 36$
• $2\ →\ 1\ →\ 3$: $6\ +\ 15\ =\ 21$

$3$ 条哈密顿路径权值均不相同，符合条件。