Description

Before the cows go home to rest and have fun, Farmer John wants them to get some mental exercise by playing a game.

The game board consists of $n$ identical holes, and all holes are initially empty. A cow may either cover an empty hole with a rock, or uncover a hole that was previously covered. A game state is defined by which holes are covered by rocks.

The goal of the game is for the cow to reach every possible game state exactly once, and finally return to the initial state.

Here is an example from one of their games (empty holes are shown as O, and holes covered by rocks are shown as X):

Now the cows are stuck and cannot continue. They must uncover a hole, but no matter which hole they uncover, they will reach a state they have already visited. For example, if they remove the rock from the second hole, they will reach the state they already visited at time $2$ (X O X).

Below is a valid solution for 3 holes:

Now the cows are tired of this game, and they want you to help.

Given $n$, find a valid sequence of states for the game. If there are multiple solutions, output any one of them.

Input Format

Only one line with an integer $n$.

Output Format

Print a total of $2^n+1$ lines. Each line contains a string of length $n$ consisting only of characters O and X. The $i$-th character of the string indicates whether hole $i$ is covered or not in that state. The first and last lines must both be all O.

3

OOO
OXO
OXX
OOX
XOX
XXX
XXO
XOO
OOO

Hint

Explanation for Sample 1

See the problem description.

Constraints

For $100\%$ of the testdata, $1\le n\le15$.

Translated by ChatGPT 5