The Rock Game

Before the cows head home to rest, Farmer John wants them to get some intellectual stimulation by playing a game.

The board has $N$ ($1 \le N \le 15$) identical holes in the ground, numbered $1$ through $N$ from left to right. Every hole starts uncovered. In one move a cow either covers exactly one currently uncovered hole with a rock, or uncovers exactly one currently covered hole.

The state of the game is described by which holes are covered and which are not: a string of length $N$ whose $j$-th character is X if hole $j$ is covered and O if it is uncovered. There are $2^N$ possible states.

The cows want to begin from the all-uncovered state, visit every one of the $2^N$ states exactly once, and then return to the all-uncovered state. Because each move flips exactly one hole, such a tour changes one character at a time and closes back onto its start.

Reaching every state is not automatic. For example, with $N = 3$ a cow can play seven moves and arrive at state XXX, only to find that uncovering any single hole leads to a state it has already visited — the tour gets stuck before it can return to OOO.

Many valid tours exist. To make the answer unique, you must output one specific canonical tour, defined below in the Output section.

The single line contains one integer $N$ ($1 \le N \le 15$).

Print exactly $2^N + 1$ lines. Line $t + 1$ (for $t = 0, 1, \ldots, 2^N$) is the state at time $t$ of the required canonical tour, the reflected binary Gray-code cycle:

• Let $m = t \bmod 2^N$ and $g = m \oplus \lfloor m / 2 \rfloor$ (the bitwise XOR of $m$ with $m$ shifted right by one bit).
• Write $g$ as an $N$-bit binary number, most significant bit first. Hole $1$ is the most significant bit and hole $N$ is the least significant bit.
• Print X for each bit equal to $1$ (covered) and O for each bit equal to $0$ (uncovered).

Since $g = 0$ at both $t = 0$ and $t = 2^N$, the first and last lines are always all O. Consecutive lines always differ in exactly one hole, and the states on lines $1$ through $2^N$ are all distinct.