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

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

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

For example: in the figure below, $v_2 \rightarrow v_3 \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 the length of any monotonically increasing path in the figure below does not exceed $3$.

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

Conclusion: Suppose a weighted undirected graph $G$ has $100$ vertices and $1000$ edges, and all edge weights are distinct. Then, there must exist a monotonically increasing path in $G$ with a length of at least $20$.

Proof: Assume there is an explorer at each vertex. We enumerate all edges in increasing order of their weights, and each time we swap the positions of the explorers at the endpoints of the current edge. It can be seen that each explorer traverses a monotonically increasing path. Additionally, since there are $100$ explorers and they take a total of $2000$ steps, at least one person must have taken $20$ steps. Q.E.D.

Now, our problem is:

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

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

Input

The input consists of a single line containing a positive even integer $N$.

Output

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)$, ..., the $N$-th number is the weight for $(1,N)$; then the weights for $(2,3)$, $(2,4)$, ..., $(2,N)$; then the weights for $(3,4)$ to $(3,N)$; and so on; finally, the weight for $(N-1,N)$.

Examples

Input 1

4

Output 1

4 6 2
3 1
5

Input 2

6

Output 2

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

Subtasks

For $20\%$ of the data, $2 \leq N \leq 20$;

For $50\%$ of the data, $2 \leq N \leq 100$;

For $100\%$ of the data, $2 \leq N \leq 500$.

In addition to the specific characteristics of different test cases, you may also receive partial points for each test case. If your program terminates correctly and outputs in the specified format, we will score it as follows:

Let $A$ be the length of the longest monotonically increasing path in your graph, and $B$ be the length of the optimal answer.

If $A=B$, you will receive $10$ points;

If $B < A < 2B$, you will receive $3$ points;

If $A \geq 2B$, you will receive $0$ points.

Note

This problem provides an additional file named daydayup.tab.

This file contains $50$ tables. Each of these tables satisfies a very special property.

You may examine these tables. If they are helpful to you, you can read this file in your program.

Of course, you have another option, which is to ignore this file entirely. Even so, you can still solve this problem.

During evaluation, this file will be in the same directory as your program, just like the input file, and its filename will not change.

Please note: Do not paste this file directly into your code or store it as a large constant table, otherwise your code length may exceed the competition's code length limit and will not be evaluated.