돌 놓기 게임

소들이 쉬러 가기 전에, 농부 존은 소들에게 게임을 시켜 머리를 쓰게 하려고 합니다.

땅에는 왼쪽부터 $1$번부터 $N$번까지 번호가 매겨진, 똑같이 생긴 구멍이 $N$개 ($1 \le N \le 15$) 있습니다. 처음에는 모든 구멍이 덮여 있지 않습니다. 한 번의 이동에서 소는 덮여 있지 않은 구멍 하나를 골라 돌로 덮거나, 이미 덮인 구멍 하나를 골라 걷어냅니다.

게임의 상태는 어떤 구멍이 덮였고 어떤 구멍이 덮이지 않았는지로 정해집니다. 길이 $N$의 문자열로 나타내며, $j$번째 문자는 $j$번 구멍이 덮였으면 X, 덮이지 않았으면 O입니다. 가능한 상태는 모두 $2^N$가지입니다.

소들은 모든 구멍이 덮이지 않은 상태에서 출발하여, $2^N$개의 상태를 정확히 한 번씩 모두 방문한 뒤, 다시 모든 구멍이 덮이지 않은 상태로 돌아오려고 합니다. 한 번의 이동은 정확히 한 구멍만 바꾸므로, 이런 순회는 한 글자씩만 바뀌며 처음 상태로 되돌아옵니다.

모든 상태를 방문하는 것이 항상 가능한 것은 아닙니다. 예를 들어 $N = 3$일 때, 소가 일곱 번 이동해 XXX 상태에 도달했는데, 어떤 구멍을 걷어내도 이미 방문한 상태로만 갈 수 있어 OOO로 돌아오지 못하고 막혀 버릴 수 있습니다.

유효한 순회는 여러 가지가 있습니다. 답을 하나로 정하기 위해, 아래 출력 항목에 정의된 하나의 정해진 순회를 출력해야 합니다.

한 줄에 정수 $N$ ($1 \le N \le 15$) 하나가 주어집니다.

정확히 $2^N + 1$개의 줄을 출력합니다. $t + 1$번째 줄 ($t = 0, 1, \ldots, 2^N$)은 정해진 정규 순회에서 시각 $t$의 상태이며, 반사 이진 그레이 코드(reflected binary Gray code) 순환으로 정의됩니다.

• $m = t \bmod 2^N$, $g = m \oplus \lfloor m / 2 \rfloor$로 둡니다. 여기서 $\oplus$는 $m$과, $m$을 오른쪽으로 한 비트 밀 값의 비트별 XOR입니다.
• $g$를 $N$비트 이진수로, 최상위 비트부터 씁니다. $1$번 구멍이 최상위 비트, $N$번 구멍이 최하위 비트에 대응합니다.
• 각 비트가 $1$이면 (덮임) X, $0$이면 (덮이지 않음) O를 출력합니다.

$t = 0$과 $t = 2^N$에서 모두 $g = 0$이므로, 첫 줄과 마지막 줄은 항상 모두 O입니다. 인접한 두 줄은 항상 정확히 한 구멍만 다르며, $1$번째부터 $2^N$번째 줄까지의 상태는 모두 서로 다릅니다.