这是一个交互式问题。在这个问题中,你需要战胜一个随机做出移动的对手。
Felix 和 Sophia 在一个由 $m \times n$ 个正方形格子组成的矩形棋盘上玩游戏。他们轮流进行操作。棋盘上的每个格子要么是空白的,要么是被染色的。最初,所有格子都是空白的。一次移动包括选择任意四个组成 $2 \times 2$ 正方形的空白格子,并将这些格子染色。无法进行移动的玩家输掉游戏。
在 Felix 的每个回合中,他会从所有可能的 $2 \times 2$ 正方形中等概率随机选择一个并将其染色。你的任务是扮演 Sophia。如果你的程序在 300 局游戏中输掉不超过 10 局,则被认为是正确的。
在这个问题中,每个测试点都指定了棋盘的大小。在每个测试点中,你必须恰好玩 300 局游戏。在每局游戏中,Felix 先手,Sophia 后手。
输入格式
第一行包含两个由空格分隔的整数 $m$ 和 $n$:棋盘的大小($16 \le m, n \le 25$)。请注意下限:棋盘不能太小。棋盘的行从 $1$ 到 $m$ 编号,列从 $1$ 到 $n$ 编号。
接下来的输入被分为若干个块,每个块对应一局游戏。每个块以一行 start k 开始,其中 $k$ 是从 1 开始的游戏编号。接下来的每一行格式为 move r c($1 \le r < m, 1 \le c < n$)。这样的一行意味着在 Felix 的回合中,他将坐标为 $(r, c)$、$(r, c + 1)$、$(r + 1, c)$ 和 $(r + 1, c + 1)$ 的四个格子染了色。如果一局游戏以 Sophia 获胜结束,则在 Felix 的下一个回合位置给出的行将是 won,之后该块结束。如果一局游戏以 Felix 获胜结束,则在 Felix 的回合之后的下一行将是 lost,之后该块也结束。
各个块一个接一个地出现,没有任何额外的分隔符。在最后一个块之后,有一行单独的 end。
保证 Felix 的所有移动都符合游戏规则,且每次移动都是伪随机且等概率选择的。值得注意的是,在第一局游戏开始之前,伪随机数生成器总是使用相同的值进行初始化。这意味着,如果你的程序作为 Sophia 的策略是确定性的,那么在每次测试中,如果重复运行该程序,所有的移动和所有游戏的结果都将保持不变。
输出格式
在游戏中的每个 Sophia 的回合,且至少存在一个可行移动时,输出一行格式为 move r c($1 \le r < m, 1 \le c < n$)。这样的一行意味着你为 Sophia 选择的移动是将坐标为 $(r, c)$、$(r, c + 1)$、$(r + 1, c)$ 和 $(r + 1, c + 1)$ 的四个格子染色。
为了防止输出缓冲,在输出每行后,请务必执行清空缓冲区的命令。例如,在 C 或 C++ 中可以使用 fflush(stdout),在 Java 中可以使用 System.out.flush(),在 Pascal 中可以使用 flush(output),在 Python 中可以使用 sys.stdout.flush()。
如果你的程序做出了无效的移动,或者输掉了超过 10 局游戏,它将在相应的测试点上获得 “Wrong Answer” 的结果。
样例
输入格式 1
2 5 start 1 move 1 4 <waiting for output> won start 2 move 1 2 <waiting for output> won end
输出格式 1
<reading input> <reading input> <reading input> move 1 1 <reading input> <reading input> <reading input> move 1 4 <reading input> <terminating>
说明
当评测你的程序时,第一个测试点就是题面中的样例。请注意,该测试点不满足 $m, n \ge 16$ 的限制,但从第二个测试点开始的所有测试点均满足该限制。此外,在样例测试点中,只有 2 局游戏,而不是其他所有测试点中的 300 局游戏。Felix 的移动选择不依赖于 Sophia 的移动,并且是预先确定的。最后,在 $2 \times 5$ 的棋盘上,无论游戏如何进行,后手(Sophia)都必胜。
如果你的程序赢得了两局游戏并在此之后成功终止,则可以通过样例测试。回想一下,对于正式测试点,你的程序需要输掉不超过 10 局游戏并成功终止才能通过。