D - Classified

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 600

問題文

AtCoder 本社は N 室の部屋からなる施設であり、部屋には 1 から N の番号がついています。どの 2 部屋の間にも、それらを直接結ぶ通路が 1 本通っています。

社長の高橋君はセキュリティのため、全ての通路に レベル を設定するようあなたに依頼しました。ここで、レベルは正の整数値であり、以下の条件を満たさなければなりません。

  • 全ての部屋 i\ (1 \leq i \leq N) について、部屋 i から出発し、レベルが等しい通路のみをいくつか通って部屋 i に戻るとき、通路を通る回数は必ず偶数になる。

あなたの仕事は、通路ごとのレベルをうまく設定して、レベルの最大値を最小化することです。

制約

  • N2 以上 500 以下の整数

入力

入力は以下の形式で標準入力から与えられます。

N

出力

目的を達成するような設定の仕方を次のように出力してください。

a_{1,2} a_{1,3} ... a_{1,N}
a_{2,3} ... a_{2,N}
.
.
.
a_{N-1,N}

ここで、a_{i,j} は部屋 i と部屋 j の間の通路に設定するレベルです。

答えが複数ありえる場合、どれを出力してもかまいません。


入力例 1

3

出力例 1

1 2
1

この出力例は下の画像のようになります。

たとえば部屋 2 から出発して、2 \to 3 \to 2 \to 3 \to 2 \to 1 \to 2 という経路でレベル 1 の通路のみを通って元の部屋に戻るとき、通路を通る回数は 6 回です。

Score: 600 points

Problem Statement

AtCoder's head office consists of N rooms numbered 1 to N. For any two rooms, there is a direct passage connecting these rooms.

For security reasons, Takahashi the president asked you to set a level for every passage, which is a positive integer and must satisfy the following condition:

  • For each room i\ (1 \leq i \leq N), if we leave Room i, pass through some passages whose levels are all equal and get back to Room i, the number of times we pass through a passage is always even.

Your task is to set levels to the passages so that the highest level of a passage is minimized.

Constraints

  • N is an integer between 2 and 500 (inclusive).

Input

Input is given from Standard Input in the following format:

N

Output

Print one way to set levels to the passages so that the objective is achieved, as follows:

a_{1,2} a_{1,3} ... a_{1,N}
a_{2,3} ... a_{2,N}
.
.
.
a_{N-1,N}

Here a_{i,j} is the level of the passage connecting Room i and Room j.

If there are multiple solutions, any of them will be accepted.


Sample Input 1

3

Sample Output 1

1 2
1

The following image describes this output:

For example, if we leave Room 2, traverse the path 2 \to 3 \to 2 \to 3 \to 2 \to 1 \to 2 while only passing passages of level 1 and get back to Room 2, we pass through a passage six times.