你正在一个拥有大型舰船的广阔海洋中玩《战舰》游戏。更准确地说，这里有一个最大尺寸为 $100 \times 100$ 的大型方格网，其中放置了最多 10 艘《战舰》中最大类型的舰船——航空母舰。每艘航空母舰的长度为 5 个格子，可以水平或垂直放置。舰船之间不会重叠，但允许相邻。参见图 L.1 和图 L.2 了解示例。

《战舰》游戏原版，在升级到 100 × 100 网格之前。

图 L.1：前四次射击后的交互示例 1 说明。

不幸的是，你的对手似乎会随心所欲地修改规则。看起来他们并不总是在你开始射击前就确定舰船的位置。你并没有被他们这种作弊行为所困扰，并决定无论如何都要尝试赢得比赛。

你的目标是在最多 2500 次射击内定位并击沉对手所有的航空母舰，也就是说，你必须击中对手所有舰船的全部 5 个格子。

交互

这是一个交互式问题。你的程序将针对一个交互器运行，交互器会读取你程序的标准输出并向你程序的标准输入写入内容。此交互需要遵循特定的协议：

交互器首先发送一行，包含两个整数 $n$ 和 $k$ ($5 \le n \le 100, 1 \le k \le 10$)，分别表示网格的大小和舰船的数量。保证在网格中放置 $k$ 艘互不重叠的航空母舰是可能的。

然后，你的程序需要开始射击。每次射击通过打印一行格式为 “$x$ $y$” ($1 \le x, y \le n$) 的内容来完成，表示你射击位置 $(x, y)$。交互器将回复 “hit” 表示击中，“sunk” 表示该次射击导致一艘航空母舰沉没，否则回复 “miss”。如果你射击了之前已经射击过的位置，回复将是 “miss”。

一旦你击沉了最后一艘航空母舰，交互将停止，你的程序必须退出。

交互器是自适应的：舰船的位置可以在交互过程中确定，并可能取决于你决定射击的位置。

请确保在每次写入后刷新缓冲区。

提供了一个测试工具来帮助你开发解决方案。

射击超过 2500 次将导致答案错误。

样例

输入格式 1

7 2
miss
hit
miss
hit
hit
hit
hit
sunk
miss
miss
hit
miss
hit
hit
sunk

输出格式 1

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