这是一个交互式问题。
在一个无聊的周二晚上，Jack 和 Jill 决定下一盘国际象棋。由于 Jack 的棋艺非常平庸，Jill 承诺在她的回合中随机走棋。形式化地说，如果 Jill 的回合有 $n$ 种合法走法，Jill 将以 $1/n$ 的概率选择每种走法。此外，Jill 非常喜欢黑色。因此，她所有的对局都执黑棋。在输掉几局后，Jack 请你编写一个程序来帮助他击败 Jill 的随机策略。
国际象棋规则
本节基于维基百科关于国际象棋的文章。
国际象棋棋子分为白棋和黑棋两组。每组由 16 枚棋子组成：一个王、一个后、两个车、两个象、两个马和八个兵。游戏在八行八列的方格棋盘上进行。64 个方格颜色交替，被称为浅色格和深色格。棋盘放置时，离每位玩家最近的右下角必须是浅色格。因此，每个后都从自己颜色的方格开始（白后在浅色格；黑后在深色格）。
白棋先走，之后双方轮流走棋，每回合移动一枚棋子（王车易位除外，此时移动两枚棋子）。棋子移动到未被占据的方格或被对方棋子占据的方格，后者会被吃掉并移出棋盘。除了“吃过路兵”外，所有棋子都是通过移动到对方棋子所在的方格来吃子。走棋是强制性的，禁止跳过回合。玩家不得做出任何会导致自身王被将军或使王处于被将军状态的走法。如果轮到走棋的玩家没有合法走法，游戏结束；结果要么是被将死（没有合法走法的玩家输），要么是逼和（如果王没有被将军，则为平局）。每种棋子都有其独特的移动方式：
- 王可以向任何方向移动一格。王还有一个特殊的走法，称为王车易位，涉及移动一个车。
- 车可以沿横线或纵线移动任意数量的方格，但不能跳过其他棋子。与王一起，车参与王的王车易位。
- 象可以沿对角线移动任意数量的方格，但不能跳过其他棋子。
- 后结合了车和象的能力，可以沿横线、纵线或对角线移动任意数量的方格，但不能跳过其他棋子。
- 马移动到最近的方格中不与当前位置在同一横线、纵线或对角线上的方格。（因此，移动形成 L 形：垂直两格水平一格，或水平两格垂直一格。）马是唯一可以跳过其他棋子的棋子。
- 兵可以向前移动到同一纵线上紧邻的未被占据的方格，或者在第一次移动时沿同一纵线前进两格，前提是这两个方格都未被占据。兵可以通过移动到相邻纵线上前方对角线的方格来吃掉对方的棋子。兵有两种特殊走法：吃过路兵和升变。
在每局游戏中，每个王都可以进行一次特殊的移动，称为王车易位。王车易位包括将王沿第一横线向位于玩家第一横线上的车移动两格，然后将车放置在王刚刚跨过的最后一个方格上。如果满足以下条件，则允许王车易位：
- 王和车在游戏过程中均未移动过。
- 王和车之间没有棋子。
- 王不能处于被将军状态，王也不能经过任何被敌方棋子攻击的方格，或移动到会导致被将军的方格。（注意：如果车受到攻击，或者车经过被攻击的方格，则允许王车易位。）
当兵从起始位置前进两步，且相邻纵线上紧邻目标方格处有对方的兵时，对方的兵可以“吃过路兵”（“in passing”），移动到该兵经过的方格。这只能在紧接着的下一回合完成；否则该权利丧失。
当兵前进到第八横线时，作为移动的一部分，它会升变，必须换成玩家选择的同色后、车、象或马。通常，兵会选择升变为后，但在某些情况下会选择其他棋子；这被称为欠升变。对升变的棋子没有限制，因此可能拥有比游戏开始时更多的同类棋子（例如，两个或更多的后）。
当王受到对方一枚或两枚棋子的直接攻击时，称为被将军。应对将军的走法只有在结果位置王不再被将军时才合法。这可能涉及吃掉将军的棋子；在将军的棋子和王之间放置一枚棋子（仅当攻击棋子是后、车或象，且其与王之间有空位时才可能）；或将王移动到未被攻击的方格。王车易位不是应对将军的合法手段。
游戏的目标是将对方将死；当对方的王被将军，且没有合法方式使其脱离攻击时，即发生将死。玩家做出任何导致自身王被将军或使王处于被将军状态的走法都是非法的。
有几种方式可以导致平局：
- 逼和：轮到走棋的玩家没有合法走法且没有被将军。
- 三次重复局面：这通常发生在双方都无法避免重复局面而不遭受不利时。在这种情况下，任何一方都可以要求平局。局面三次出现不需要在连续的回合中，要求才有效。如果所有被占据的方格和占据它们的棋子种类（不一定是同一枚棋子）相同，双方的王车易位权利没有改变，且第一次出现时没有吃过路兵的可能性（即使显然没有走），则认为两个局面相同或相等。
- 五十步规则：如果在之前的 50 回合（100 个半回合）内没有兵移动且没有吃子，任何一方都可以要求平局。半回合是白棋或黑棋的一步走法。
在本问题中，我们假设双方在可能的情况下都会要求平局。
标准代数记谱法 (SAN)
本节基于维基百科关于国际象棋代数记谱法的文章。
棋盘上的每个方格都由唯一的坐标对标识：一个字母和一个数字。垂直的方格列称为纵线，从白棋的左侧（后翼）到右侧（王翼）标记为 a 到 h。水平的方格行称为横线，从白棋一侧开始编号为 1 到 8。因此，每个方格都有一个唯一的标识，即纵线字母后跟横线数字。
每种棋子类型（兵除外）都由一个大写字母标识（K 代表王，Q 代表后，R 代表车，B 代表象，N 代表马）。兵不使用大写字母标识，而是通过缺少字母来标识。记录走法时无需区分兵，因为只有一个兵可以移动到给定的方格。
棋子的每次移动都由棋子的大写字母加上目标方格的坐标表示。例如，Qg4（将后移动到 g4）。对于兵的移动，不使用表示兵的字母，仅给出目标方格。例如，e4（将兵移动到 e4）。
当棋子吃子时，在目标方格前立即插入一个 x。例如，Bxa6（象吃掉 a6 处的棋子）。当兵吃子时，使用兵出发的纵线来标识该兵。例如，fxe7（f 纵线上的兵吃掉 e7 处的棋子）。吃过路兵通过指定吃子兵的出发纵线、x 和目标方格（而不是被吃棋子的方格）来表示。例如，exf6（e 纵线上的兵吃掉 f5 处的兵）。
当两枚（或更多）相同的棋子可以移动到同一个方格时，通过指定棋子的字母，后跟（按优先级降序）来唯一标识移动的棋子：
- 出发纵线（如果不同），例如 Nbc3，
- 出发横线（如果纵线相同但横线不同），
- 纵线和横线（如果两者单独都不足以识别棋子，这仅发生在罕见的情况下，即一个或多个兵已升变，导致玩家有三枚或更多相同的棋子可以到达同一个方格）。
如上所述，可以插入 x 来表示吃子。例如，N1xc3（当另一个白马位于 b5 时，b1 处的白马吃掉 c3 处的黑棋）。
当兵移动到最后一行并升变时，在走法记谱的末尾用等号和升变的棋子表示，例如：h8=R（升变为车）。
王车易位用特殊记谱 O-O（王翼易位）和 O-O-O（后翼易位）表示。注意使用大写字母 O。
使对方王被将军的走法在末尾附加字符 +。如果将军同时也是将死，则字符 + 被字符 # 替换。
交互协议
每一行输入描述一个输入命令。每个命令由命令类型和命令参数组成，中间用冒号和一个空格隔开。有三种不同类型的输入命令：
black_move: <last-black-move>
white_moves: <move-list>
result: <verdict>
游戏以 white_moves 命令开始，列出最初可能的走法：<move-list> 是以空格分隔的合法白棋走法列表，顺序不固定。
在每一回合，你的程序应从给定的 move-list 中选择一个合法的白棋走法，并将其输出在一行上。
之后，如果游戏在你的程序走棋后结束，则发送 result 命令。否则，发送一个 black_move 命令，描述黑棋的走法（回想一下，它是从所有合法走法中均匀随机选择的）。
之后，如果游戏在黑棋走棋后结束，则发送 result 命令。否则，再次发送 white_moves 命令，列出当前所有可用的走法（顺序不固定），然后轮到你的程序走棋。
你的程序在收到 result 命令后应终止。共有六种不同类型的判决（游戏终止状态）：
<verdict> |
result | <verdict> |
result |
|---|---|---|---|
| White won by checkmate | OK | Illegal move | PE |
| Game drawn by stalemate | WA | Game drawn by repetition | WA |
| Game drawn by fifty-move rule | WA | Black won by checkmate | WA |
打印每一行后，请刷新输出缓冲区，否则你将得到 Idleness Limit Exceeded 的结果：这可以通过调用例如 C 或 C++ 中的 fflush (stdout)，Java 中的 System.out.flush ()，或 Python 中的 sys.stdout.flush () 来完成。
共有 150 个不同的测试。在每个测试中，用于生成走法的伪随机数生成器的初始状态是预先固定的。测试 1 对应于样例。
样例
输入 1
white_moves: a3 a4 b3 b4 c3 c4 d3 d4 e3 e4 f3 f4 g3 g4 h3 h4 Nh3 Na3 Nc3 Nf3 black_move: c5 white_moves: a3 a4 b3 b4 c3 c4 d3 d4 f3 f4 g3 g4 h3 h4 e5 Bc4 Nc3 Ba6 Qh5 Nf3 Ke2 Na3 Bb5 Qe2 Ne2 Nh3 Bd3 Be2 Qf3 Qg4 black_move: Na6 white_moves: a3 a4 b3 b4 c3 c4 d3 d4 f3 f4 g3 g4 h3 h4 e6 Bc4 Nc3 Bxa6 Qh5 Nf3 Ke2 Na3 Bb5 Qe2 Ne2 Nh3 Bd3 Be2 Qf3 Qg4 black_move: g5 white_moves: a3 a4 b3 b4 c3 c4 d3 d4 f3 f4 g3 h3 h4 e6 Bc4 Nc3 Qh5 Be2 Ke2 Na3 Bb5 Kf1 Qe2 Ne2 Nh3 Bd3 Bf1 Bxb7 Nf3 Qf3 Qg4 black_move: f5 white_moves: a3 a4 b3 b4 c3 c4 d3 d4 f3 f4 g3 h3 h4 e6 exf6 Nc3 Qa4 Qd4 Qe2 Ne2 Qf3 Qb4 Qxg5 Na3 Qf4 Qc4 Kf1 Qd1 Qg3 Qh5# Qxf5 Bb5 Qe4 Bd3 Qh4 Bf1 Be2 Qh3 Ke2 Nh3 Kd1 Bxb7 Nf3 Bc4 black_move: b5 white_moves: a3 a4 b3 b4 c3 c4 d3 d4 f3 f4 g3 h3 h4 fxe7 f7+ Nc3 Qa4 Qd4 Qe2 Ne2 Qf3 Qb4 Qxg5 Na3 Qf4 Qc4 Kf1 Qe6 Qd1 Qg3 Qh5# Qf5 Bxb5 Qe4 Qxd7+ Qh4 Bxc8 Qh3 Ke2 Nh3 Kd1 Bb7 Nf3 black_move: Rb8 white_moves: a3 a4 b3 b4 c3 c4 d3 d4 f3 f4 g3 h3 h4 fxe7 f7+ O-O Nbc3 Nec3 Qa4 Qd4 Nd4 Qf3 Qb4 Rg1 Qxg5 Na3 Qf4 Qc4 Kf1 Ng1 Qe6 Qg3 Qh5# Qf5 Bxb5 Ng3 Qe4 Rf1 Qxd7+ Qh4 Bxc8 Qh3 Nf4 Kd1 Bb7 result: White won by checkmate
输出 1
e4 e5 Bxa6 Qg4 exf6 Ne2 Qh5#
说明
在上面的例子中，你可以看到一次吃过路兵（5. exf6）。此外，在白棋第 7 步，有消歧走法（Nbc3 和 Nec3）和王车易位（O-O）的例子。