이진 부호화

이진 부호화는 $0$부터 $2^n - 1$까지의 각 정수를 정확히 $n$개의 비트로 나타내며, 각 비트는 $0$ 또는 $1$이다. 가장 큰 자리(최상위 비트)를 먼저 쓰고, 두 부호를 비교할 때는 최상위 비트부터 최하위 비트 방향으로 왼쪽에서 오른쪽으로 비교한다. 부호는 정수를 오름차순으로 나열했을 때 그 부호들도 오름차순이 되도록 배정한다. 예를 들어 $0$부터 $7$까지의 이진 부호화는 다음과 같다.

절단 이진 부호화는 이를 일반화하여 $0$부터 $m - 1$까지의 정수를 나타내는데, 이때 $m$은 어떤 $n$에 대해서도 $2^n$과 같지 않을 수 있다. 보통의 이진 부호화와 달리, 서로 다른 정수를 나타낼 때 서로 다른 개수의 비트를 사용할 수 있다. $m \le 2^n$을 만족하는 가장 작은 정수를 $n$이라 하자. 그러면 절단 이진 부호화는 각 정수를 $n$개 또는 $n - 1$개의 비트로 나타낸다. 어떤 정수가 $n - 1$개의 비트만 사용하는 경우는 오직 $m < 2^n$일 때뿐이며, $m = 2^n$이면 절단 이진 부호화는 보통의 이진 부호화와 같아진다. 절단 이진 부호도 이진 부호와 마찬가지로 왼쪽에서 오른쪽으로 비교한다.

절단 이진 부호화는 다음 규칙도 만족한다.

• 작은 정수는 큰 정수와 같거나 더 적은 개수의 비트를 사용한다.
• 정수를 오름차순으로 나열하면 그 부호들도 오름차순이 된다.
• $0$부터 $m - 1$까지의 정수에 대한 부호는 모두 서로 다르다.
• $n - 1$개의 비트로 된 어떤 부호도 $n$개의 비트로 된 부호의 접두사가 되지 않는다.
• $0$부터 $m - 1$까지의 정수를 나타내는 데 쓰이는 전체 비트 수가 최소이다.

예를 들어 $0$부터 $5$까지의 절단 이진 부호화는 다음과 같다.

$0$부터 $m - 1$까지의 정수를 절단 이진 부호화로 부호화하라.

입력은 정수 $m$ 하나를 포함한다 ($2 \le m \le 10000$).

$m$개의 줄을 출력한다. $0$부터 $m - 1$까지의 각 $i$에 대해, $i$번째 줄에는 정수 $i$의 절단 이진 부호를 출력한다. 따라서 부호들은 그것이 나타내는 정수의 오름차순으로 출력된다.