配点: $900$ 点

問題文

Diverta City は $N$ 個の街からなる新しい都市であり、街には番号が $1, 2, ..., N$ と付けられています。

市長のりんごさんは、すべての $2$ つの街の組を $1$ つの双方向の道路で結ぶ計画です。それぞれの道路の長さはまだ決まっていません。

ある街から出発して、他のすべての街を一度ずつ訪れる経路を「ハミルトン経路」と呼びます。ここで、あるハミルトン経路を逆にたどった経路は、元のハミルトン経路と同じものとして扱います。

ハミルトン経路は $N! / 2$ 種類あり、そのすべての全長 (経路上の道路の長さの合計) が異なるようにして、多様性のある都市をつくりたいです。

そのような道路の長さの組み合わせを $1$ つ見つけてください。ただし、次の条件を満たさなければならないです。

• 道路の長さはすべて 正の整数
• 道路が長すぎても建設コストが大きくなるので、それぞれのハミルトン経路の全長を $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)$

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

3

0 6 15
6 0 21
15 21 0

ハミルトン経路は $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$

この $3$ つの歩行距離はすべて異なるので、条件を満たします。

4

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

ハミルトン経路は $12$ 通りあり、歩行距離はすべて異なります。