题目描述

在奶牛回家休息和娱乐之前，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$。