题目描述

在奶牛回家休息和娱乐之前，Farmer John 希望它们通过玩游戏获得一些智力上的刺激。

游戏板由 $n$ 个相同的洞组成，这些洞最初都是空的。一头母牛要么用石头盖住一个空的洞，要么揭开一个先前被盖住的洞。游戏状态的定义是所有洞是否被石头覆盖的情况。

游戏的目标是让奶牛到达每个可能的游戏状态一次，最后回到初始状态。

以下是他们其中一次游戏的示例（空的洞用 O 表示，用石头盖住的洞用 X 表示）：

现在牛被卡住玩不下去了！他们必须打开一个洞，然而不管他们打开哪个洞，他们都会到达一个他们已经到达过的状态。例如，如果他们从第二个洞中取出岩石，他们将到达他们在时刻 $2$ 已经访问过的状态（X O X）。

下面是一个 3 个孔的有效解决方案：

现在，奶牛们厌倦了这个游戏，它们想找你帮忙。

给定 $n$，求游戏的有效解决方案序列。如果有多个解决方案，则输出任意一个。

输入格式

仅一行，一个整数 $n$。

输出格式

共 $2^n+1$ 行，每行一个长度为 $n$ 的字符串，其中只包含字符 O 和 X，该行中的第 $i$ 个字符表示第 $i$ 个孔在此状态下是被覆盖还是未覆盖，第一行和最后一行必须全部都是 O。

3

OOO
OXO
OXX
OOX
XOX
XXX
XXO
XOO
OOO

提示

样例 1 说明

见题目描述。

数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le15$。