Problem Description

For a weighted undirected graph, we can examine its monotonically increasing paths.

A path is called monotonically increasing if the weights along it are strictly increasing.

Note that a path consists of multiple edges connected end-to-end and can pass through the same vertex multiple times. The length of the path is the number of edges it contains.

For example: In the graph below, the path $v_2 \rightarrow v_4 \rightarrow v_1 \rightarrow v_2$ is a monotonically increasing path because the weights of the edges are $1, 2, 4$. The length of this path is $3$. Furthermore, you can verify that all monotonically increasing paths in this graph have lengths not exceeding $3$.

The following conclusion states that in some graphs, there always exists a relatively long monotonically increasing path:

Conclusion: Suppose a weighted undirected graph $G$ has $100$ nodes and $1000$ edges, with all weights being distinct. Then, $G$ must have a monotonically increasing path with a length greater than or equal to $20$.

Proof: Assume there is an explorer at each node. We enumerate all edges in ascending order of their weights and swap the positions of the explorers at the connected nodes. It can be seen that each explorer walks along a monotonically increasing path. Additionally, since there are $100$ explorers and they collectively walk $2000$ steps, someone must have walked $20$ steps. Q.E.D.

Now, our problem is:

Given a complete graph $G$ with an even number $N$ of vertices.

Your task is to assign a distinct weight to each edge such that the length of the longest monotonically increasing path is minimized.

Input Format

Input consists of a single line containing a positive even number $N$.

Output Format

Output a permutation of the integers from $1$ to $\frac{N(N-1)}{2}$, separated by spaces or newlines.

The first number represents the weight assigned to edge $(1,2)$; the second number is the weight for $(1,3)$, and so on; the $N$-th number is the weight for $(1,N)$; then comes the weight for $(2,3)$, $(2,4)$, ..., $(2,N)$; followed by the weights for $(3,4)$ to $(3,N)$; and so on; finally, the weight for $(N-1,N)$.

Sample Input and Output

Sample Input #1

4

Sample Output #1

4 6 2
3 1
5

Sample Input #2

6

Sample Output #2

12 8 15 3 5
6 7 1 13
10 14 11
4 2
9

Notes

Data Size and Constraints

• For $20\%$ of the data, $N \leq 20$;
• For $50\%$ of the data, $N \leq 100$;
• For $100\%$ of the data, $2 \leq N \leq 500$.

Scoring

Apart from different characteristics for different test cases, you may also receive partial points for each test case. If your program terminates correctly and outputs in the correct format, we will score it as follows:

Suppose the length of the longest monotonically increasing path in your graph is $A$, and the correct answer is $B$.
- If $A = B$, you get $10$ points;
- If $B < A < 2B$, you get $3$ points;
- If $A \geq 2B$, you get $0$ points.

见题面 Input 部分

见题面 Output 部分