Binary Encoding

Binary encoding represents each integer from $0$ to $2^n - 1$ using exactly $n$ bits, where every bit is $0$ or $1$. The most significant bit is written first, and two codes are compared from left to right, from the most significant bit to the least significant one. Codes are assigned so that when the numbers are listed in ascending order, their codes are also in ascending order. For example, the binary encoding of the numbers $0$ to $7$ is:

Truncated binary encoding generalizes this to represent the integers from $0$ to $m - 1$, where $m$ need not equal $2^n$ for any $n$. Unlike ordinary binary encoding, it may use a different number of bits for different numbers. Let $n$ be the smallest integer with $m \le 2^n$. Then truncated binary encoding represents each number using either $n$ or $n - 1$ bits. Some numbers use only $n - 1$ bits, and this happens only when $m < 2^n$; when $m = 2^n$ the encoding is the same as ordinary binary encoding. Truncated binary codes are compared from left to right, just like binary codes.

Truncated binary encoding also satisfies the following rules:

• Smaller numbers use the same number of bits as, or fewer bits than, larger numbers.
• When the numbers are listed in ascending order, their codes are also in ascending order.
• The codes for the numbers $0$ to $m - 1$ are all distinct.
• No code with $n - 1$ bits is a prefix of any code with $n$ bits.
• The total number of bits used for the numbers $0$ to $m - 1$ is minimal.

For example, the truncated binary encoding of the numbers $0$ to $5$ is:

Encode the numbers from $0$ to $m - 1$ using truncated binary encoding.

The input contains a single integer $m$ ($2 \le m \le 10000$).

Print $m$ lines. For each $i$ from $0$ to $m - 1$, the line at position $i$ must contain the truncated binary code of the number $i$, so the codes are printed in ascending order of the numbers they represent.