이진 문자열 나열

니콜라가 수학 시간에 질문을 끝없이 던지자, 선생님은 반 전체에 다음 과제를 냈다.

길이가 $N$인 이진 문자열은 모두 $2^N$개다. 이 $2^N$개를 한 줄에 하나씩, 각 문자열이 정확히 한 번씩만 나오도록 나열한다. 이때 이웃한 두 줄의 거리가 항상 1이어야 한다.

두 이진 문자열의 거리는 같은 위치의 값이 서로 다른 자리의 개수다. 예를 들면 다음과 같다.

• 거리(111, 000) = 3 (첫째, 둘째, 셋째 자리가 다르다)
• 거리(111100, 101010) = 3 (둘째, 넷째, 다섯째 자리가 다르다)
• 거리(110011, 110011) = 0

조건을 만족하는 나열은 여러 가지다. 이 문제에서는 그중 하나만 정답으로 인정한다. 줄 번호를 0부터 세어, $i$번째 줄에는 $i \oplus \lfloor i/2 \rfloor$를 $N$자리 이진수로 쓴다. 여기서 $\oplus$는 비트 단위 배타적 논리합이고, 자리가 모자라면 앞을 '0'으로 채운다. 이 나열이 반사 이진 그레이 코드이며, 이웃한 두 줄은 정확히 한 자리에서만 다르다.

첫째 줄에 이진 문자열의 길이 $N$이 주어진다. ($1 \le N \le 16$)

$2^N$개의 줄을 출력한다. $i$번째 줄 ($0 \le i < 2^N$)에는 $i \oplus \lfloor i/2 \rfloor$의 $N$자리 이진 표현을 출력한다. 각 줄은 '0'과 '1'로만 이루어진 정확히 $N$자리여야 한다.

해가 적어도 하나는 항상 존재한다고 가정할 수 있다.