题目描述

Diverta City 是一个由 $N$ 个编号为 $1, 2, ..., N$ 的城镇组成的新城市。

市长Ringo计划用双向道路连接每对不同的城镇。每条道路的长度未确定。

_Hamilton路径_是从其中一个城镇开始，并且恰好访问每个其他城镇一次的路径。Hamilton路径的反转被认为与原始Hamilton路径相同。

共有 $N! / 2$ 种Hamilton路径。Ringo希望所有这些路径的总长度（路径上各道路长度之和）都不同，以使得这座城市多样化。

在以下条件下，找到这样一组道路长度：

• 每条道路的长度必须是正整数。
• Hamilton路径的最大总长度必须不超过 $10^{11}$。

约束条件

• $N$ 是一个介于 $2$ 和 $10$（含）之间的整数。

输入

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

$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

3

示例输出 1

0 6 15
6 0 21
15 21 0

共有三条Hamilton路径，其总长度如下：

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

它们互不相同，因此满足要求。

示例输入 2

4

示例输出 2

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

共有 $12$ 条Hamilton路径，其总长度互不相同。