题目描述

Diverta City 是由 $N$ 个城市组成的新城市，每个城市编号为 $1, 2, \ldots, N$。

市长りんご计划用一条双向道路连接所有两两城市。每条道路的长度尚未确定。

从某个城市出发，依次访问其他所有城市且每个城市只访问一次的路径称为“哈密顿路径”。这里，将某条哈密顿路径反向行走视为与原路径相同。

哈密顿路径共有 $N! / 2$ 种。市长希望让所有哈密顿路径的总长度（路径上所有道路长度之和）都互不相同，以打造一个多样化的城市。

请找出一种满足以下条件的道路长度分配方案：

• 所有道路长度均为正整数。
• 由于道路过长会导致建设成本过高，每条哈密顿路径的总长度不得超过 $10^{11}$。

输入格式

输入从标准输入读取，格式如下：

$N$

输出格式

请输出一种满足要求的道路长度分配方案，格式如下：

$w_{1,1}\ w_{1,2}\ w_{1,3}\ \ldots\ w_{1,N}$
$w_{2,1}\ w_{2,2}\ w_{2,3}\ \ldots\ w_{2,N}$
$\vdots$
$w_{N,1}\ w_{N,2}\ w_{N,3}\ \ldots\ 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

说明/提示

限制

• $N$ 是 $2$ 到 $10$ 之间的整数。

样例解释 1

哈密顿路径共有 $3$ 种。每种路径的总长度如下：

• $1 \to 2 \to 3$：总长度为 $6 + 21 = 27$
• $1 \to 3 \to 2$：总长度为 $15 + 21 = 36$
• $2 \to 1 \to 3$：总长度为 $6 + 15 = 21$

这三种路径的总长度均不相同，满足条件。

样例解释 2

哈密顿路径共有 $12$ 种，且每种路径的总长度都不同。

由 ChatGPT 4.1 翻译