题目背景

Day 1 Problem C.

题面译自 EGOI2023 findthebox。

题目描述

本题是一道 I/O 式交互题。

玛伊是一名机器人研究员，在隆德大学工作。她了解到在大学的地下室里有一个价值连城的宝藏。宝藏就在地下深处一个空房间的箱子里。不幸的是，玛伊不能直接去找那个箱子。地下室里非常黑，且带着灯去会引起怀疑。她找到宝藏的唯一办法就是遥控住在地窖里的吸尘器机器人。

地下室是一个 $H\times W$ 的网格，其中行从 $0$ 到 $H-1$（从上到下）编号，列从 $0$ 到 $W-1$（从左到右）编号，也就是说左上角格子是 $(0,0)$，右下角格子是 $(H-1,W-1)$。装宝藏的箱子在与 $(0,0)$ 不同的某个未知的格子中。每天晚上，吸尘器机器人从左上角格子开始在地下室中移动。

每天晚上，玛伊给机器人一系列指令以指导机器人移动，指令是一个包含字符 <、>、^ 和 v 的字符串。形式化地，如果机器人在格子 $(r,c)$ 且四周未被遮挡，< 使得机器人向左移动到 $(r,c-1)$，> 使得机器人向右移动到 $(r,c+1)$，^ 使得机器人向上移动到 $(r-1,c)$，v 使得机器人向下移动到 $(r+1,c)$。

地下室的墙十分坚硬，因此如果机器人试图移动到格子外，什么都不会发生。箱子也十分坚硬，并且不能被推动。在每晚结束时，机器人会报告它的位置，并回到左上角格子。

时间就是金钱，因此玛伊需要用尽量少的晚上找到箱子。

输出格式

本题是一道 I/O 式交互题。

• 在开始时，你的程序应当输入一行两个整数 $H,W$，表示格子的高度和宽度。
• 之后，你的程序与交互库交互。在每一轮交互过程中，你应当输出一个问号 ?，其后是一个非空字符串 $s$ 包含字符 <、>、^ 和 v。字符串的长度必须至多为 $2\times10^4$。然后，你的程序输入两个整数 $r,c$（$0\le r\le H-1$，$0\le c\le W-1$），表示执行完指令后机器人的位置。注意每次询问后，机器人都会回到 $(0,0)$。
• 当你知道箱子的位置时，输出 ! 和两个整数 $r_b,c_b$（$0\le r_b\le H-1$，$0\le c_b\le W-1$），表示箱子的坐标。在这之后，你的程序必须不再进行任何询问并退出。这个最终的输出在计算你的得分时不被计入询问次数。

请确保在每次询问后刷新输出流，否则你的程序可能被判定为 TLE。在 Python 中，print() 自动刷新输出流。在 C++ 中，cout << endl; 在输出换行后也会刷新输出流；如果使用 printf，请使用 fflush(stdout)。

交互库不自适应，意味着箱子的位置在交互开始前被确定。

4 5

0 2

3 4

? vv>>>>>><^^^^^>

? >>>>>>>>vvvvvvvvvv

! 2 3

提示

样例解释

考虑样例。格子有高度 $H=4$ 和宽度 $W=5$，箱子在 $(r,c)=(2,3)$。下图展示了机器人在收到指令 ? vv>>>>>><^^^^^> 后的路径，机器人最终停在 $(r,c)=(0,2)$。在第二次询问前，机器人回到左上角 $(0,0)$。程序询问 ? >>>>>>>>vvvvvvvvvv，机器人最终停在右下角 $(r,c)=(3,4)$。此时，程序决定猜答案，输出了 ! 2 3，惊喜地发现，这恰好是箱子的正确位置！

---

数据范围

对于全部数据，$1\le H,W\le 50$，箱子不会位于 $(0,0)$ 处（这意味着 $H+W\ge 3$），每次询问最多包含 $2\times 10^4$ 个指令，你可以询问至多 $2500$ 次（给出最终答案不被计入询问）。

你的程序会被测试于一定数量的测试点。如果你的程序在任何一个测试点失败（例如：给出错误的箱子坐标（WA）、程序崩了（RE）、超出时间限制（TLE）等），你会得到 $0$ 分和适当的评测结果。

如果你的程序在所有测试点都成功找到了箱子，你会得到 AC（译者注：在洛谷，非满分即为 WA），分数由下式决定：

$$\textrm{score}=\min\left(\frac{100\sqrt{2}}{\sqrt{Q}},100\right)\textrm{ 分} $$

其中 $Q$ 是所有测试点中询问次数的最大值。输出最终答案不被计入询问。分数将被四舍五入到最接近的整数。

具体地，要得到 $100$ 分，你的程序必须在 $Q=2$ 次询问内解决所有测试点。下表展示了一些 $Q$ 的值和其得分。

$Q$	$2$	$3$	$4$	$5$	$\cdots$	$20$	$\cdots$	$50$	$\cdots$	$2500$
分数	$100$	$82$	$71$	$63$	$\cdots$	$32$	$\cdots$	$20$	$\cdots$	$3$