Description

你正在一片辽阔的海洋中玩“战舰”游戏，使用的是大型战舰。 更具体地说，有一个最大为 $100\times 100$ 的正方形网格，在其中最多有 $10$ 艘“战舰”游戏中最大的舰种——航空母舰。每艘航空母舰长度为 $5$ 个格子，可以水平或垂直放置。 这些舰船不会重叠，但允许彼此相邻。参见图 L.1 示例。

:::align{center} 原始的“战舰”游戏，在升级为 $100\times 100$ 网格之前。CC BY-NC 3.0，作者 Pavel Ševela，来源 Wikimedia Commons :::

不幸的是，你的对手似乎会随心所欲地修改规则。 看起来他们并不总是在你开始射击前就确定舰船的位置。 你对他们的作弊行为并不感到惊讶，决定无论如何都要赢得这场游戏。

:::align{center} 图 L.1：示例交互 1，在前四次射击后。 :::

你的目标是在最多 $2500$ 次射击内找出并击沉所有对手的航空母舰，也就是说，你必须击中所有舰船的每一个格子（每艘船有 $5$ 个格子）。

Input Format

这是一个交互题。 你的提交将与一个“交互器”进行对话，交互器从你的标准输出读取数据，并向你的标准输入写入数据。交互过程遵循如下协议：

交互器首先输出一行两个整数 $n$ 和 $k$（$5 \le n \le 100$，$1 \le k \le 10$），分别表示网格的大小和舰船的数量。保证可以在网格中放下 $k$ 艘航空母舰且不重叠。

接下来，你的程序需要开始射击。 每次射击通过输出一行“$\texttt{x y}$”来完成（$1 \le x, y \le n$），表示你向 $(x, y)$ 位置射击。交互器会返回“$\texttt{hit}$”表示命中，“$\texttt{sunk}$”表示击沉了一艘航空母舰，“$\texttt{miss}$”表示未命中。如果你对同一位置重复射击，返回结果为“$\texttt{miss}$”。

当你击沉最后一艘航空母舰时，交互结束，你的程序应当退出。

交互器是自适应的：舰船的位置可能在交互过程中动态决定，并且可能依赖于你的射击位置。

每次输出后请确保刷新输出缓冲区。

题目提供了测试工具以帮助你开发解决方案。

如果射击次数超过 $2500$ 次，将判为错误答案。

7 2

miss

hit

miss

hit

hit

hit

hit

sunk

miss

miss

hit

miss

hit

hit

sunk

6 1

6 3

7 3

5 3

4 3

3 3

2 3

1 3

6 7

6 7

6 2

6 2

6 4

6 5

6 6

Hint

由 ChatGPT 4.1 翻译