Problem Description

Diverta City is a new city consisting of $ N $ towns, numbered $ 1, 2, ..., N $.

Mayor Ringo plans to connect every pair of towns with a bidirectional road. The lengths of these roads have not yet been determined.

A path that starts from one town and visits all other towns exactly once is called a "Hamiltonian path". Here, a path that traces back a Hamiltonian path in reverse is treated as the same as the original Hamiltonian path.

There are $ N! / 2 $ types of Hamiltonian paths, and we want all their total lengths (the sum of the lengths of the roads on the path) to be different, to create a diverse city.

Find one such combination of road lengths, subject to the following conditions:

• All road lengths are positive integers
• Each total length of a Hamiltonian path should be $ 10^{11} $ or less, as roads that are too long would increase construction costs

Input Format

The input is given from the standard input in the following format:

$ N $

Output Format

Output one combination of road lengths that achieves the goal in the following format:

$ 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} $

Here, $ w_{i, j} $ is the road connecting town $ i $ and town $ j $, and must satisfy the following conditions:

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

If there are multiple combinations of road lengths that achieve the goal, any one of them is considered correct.

Sample Input and Output

Sample Input #1

3

Sample Output #1

0 6 15
6 0 21
15 21 0

Sample Input #2

4

Sample Output #2

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

Notes/Hints

Constraints

• $ N $ is an integer between $ 2 $ and $ 10 $ inclusive

Sample Explanation 1

There are $ 3 $ types of Hamiltonian paths. The walking distances for each are as follows:
- $1 \rightarrow 2 \rightarrow 3$: Walking distance is $ 6 + 21 = 27 $
- $1 \rightarrow 3 \rightarrow 2$: Walking distance is $ 15 + 21 = 36 $
- $2 \rightarrow 1 \rightarrow 3$: Walking distance is $ 6 + 15 = 21 $
These $ 3 $ walking distances are all different, satisfying the condition.

Sample Explanation 2

There are $ 12 $ types of Hamiltonian paths, and all their walking distances are different.

见题面 Input 部分

见题面 Output 部分