Cows' Gray Code Game

Farmer John wants to give his cows some intellectual stimulation by having them play a game before they relax. The game board consists of \(n\) identical holes, which are initially all empty. A move in the game is defined as either placing a stone in an empty hole (covering it) or removing a stone from a covered hole (uncovering it). The game state is determined by which holes are covered and which are empty.

The goal is to produce a valid sequence of moves such that:

• Every possible game state (all \(2^n\) states) is visited exactly once.
• The sequence returns to the initial state (all holes empty) at the end.

This problem is equivalent to finding a Hamiltonian cycle in an \(n\)-dimensional hypercube, which is classically solved by generating a Gray code cycle. For a given integer \(n\), a Gray code sequence is a sequence of \(2^n\) binary numbers where any two consecutive numbers differ by exactly one bit. In our problem, each binary digit is mapped as follows:

• 0 corresponds to an empty hole (denoted by O).
• 1 corresponds to a covered hole (denoted by X).

For example, when \(n = 3\), one valid solution sequence is:

Your task is to write a program that, given \(n\), prints a valid solution: a sequence of game states (each state represented as a string of length \(n\) where O denotes an empty hole and X denotes a covered hole). The sequence should contain \(2^n + 1\) lines — all \(2^n\) unique states followed by the initial state again.

inputFormat

The input consists of a single integer \(n\) (\(1 \leq n \leq 16\)), representing the number of holes.

outputFormat

Output \(2^n + 1\) lines. Each line is a string of length \(n\) where each character is either O (an empty hole) or X (a covered hole). The first line should correspond to the initial state (all holes empty) and the last line should be identical to the first line.

sample

1

O
X
O