问题描述

具体描述见教材p146： 有2n（n>=4）个棋子排成一行，开始位置为白子全部在左边，黑子全部在右边。例如n=5时：OOOOO*****。移动棋子的规则是：每次必须同时移动相邻两个棋子，颜色不限，可以左移也可右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须路过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如n=5时， 成为__OOOOO*。

格式

输入

仅输入黑棋和白棋的数目n(4<=n<=1000)。

输出

输出各行每一步的移动结果，最后一行输出总移动步数，其中用“O”（大写字母）表示白棋，用“*”表示黑棋。用“__”(两个下划线）表示两个空位。

样例

5

OOOO__****O*
OOOO****__O*
OOO__***O*O*
OOO*O**__*O*
O__*O**OO*O*
O*O*O*__O*O*
__O*O*O*O*O*
step=7

限制

1s, 64MB.