当你研究古希腊神话时,你偶然发现了太阳神赫利俄斯(Helios)之子法厄同(Phaethon)的传说。在被赫利俄斯承认是其儿子后,法厄同请求驾驶他的太阳战车。尽管赫利俄斯警告他只有自己才能控制那些烈马,但赫利俄斯最终还是妥协了,将战车的控制权交给了法厄同。
悲剧的是,法厄同失去了对战车的控制,战车离地球太近,将其烧毁。 然而,你想知道故事是否会有不同的结局。如果法厄同能够到达赫利俄斯的神庙,那么战车就可以被赫利俄斯亲自停下。为此,你创建了一个符合该故事的模型。
希腊可以表示为一个二维无限网格,法厄同和他的战车从坐标 $(0, 0)$ 出发,面向 Ox 轴的正方向(即 $X$ 轴增加的方向)。赫利俄斯的神庙位于该二维网格上的一个未知位置 $(X, Y)$。初始时,战车的速度 $V$ 为 $1$。
在每个时间步,按顺序发生以下事件:
- 法厄同执行以下 3 个动作之一:将战车向左旋转 90 度、保持方向不变,或将战车向右旋转 90 度;
- 战车在它所面对的方向上移动 $V$ 个单位;
- $V$ 增加 1;
- 先知(Oracle)告诉法厄同他当前位置与赫利俄斯神庙位置之间的曼哈顿距离。
$(X_1, Y_1)$ 与 $(X_2, Y_2)$ 之间的曼哈顿距离为 $|X_1 - X_2| + |Y_1 - Y_2|$。 如果速度达到 $2 \times 10^4$,战车将失去控制并过于接近地球。如果在某一步结束时,战车恰好位于 $(X, Y)$,则战车停止。
交互
这是一个交互式问题。因此,本题不提供初始输入,你需要先进行提问。
在每一步中,你必须输出一行来操作战车的方向。该行必须符合格式 ? c,后跟一个换行符,其中 c 可以是 L(表示逆时针旋转 90 度)、R(表示顺时针旋转 90 度)或 F(表示保持方向不变)。如果不符合此格式,你将收到 WRONG-ANSWER 的判罚。
发送一行后,你必须始终清空输出缓冲区(flush)。否则,你将收到 TIMELIMIT 的判罚。
随后,先知会在标准输入中输出一个整数,表示你移动后的新位置(在指定方向移动 $V$ 个单位后)与神庙之间的曼哈顿距离。在更新位置后,$V$ 会增加。
如果该距离为 0,意味着你已经到达了赫利俄斯的神庙,因此应立即停止交互(退出程序),并获得 ACCEPTED 的判罚。
请注意,你必须在移动结束时恰好位于神庙中,仅在移动过程中飞过神庙是不算数的。
如果你的速度达到 $2 \times 10^4$,你将收到 WRONG-ANSWER 的判罚。
数据范围
- $|X| \le 10^6$
- $|Y| \le 10^6$
- $V \le 2 \times 10^4$
样例
样例输入 1
5 3 0
样例输出 1
? F ? L ? F
说明 1
在本样例中,赫利俄斯神庙(你需要猜测的位置)位于 $X=1, Y=5$。
- 初始状态:位置 $(0, 0)$,方向向右,速度 $V = 1$。
- 玩家输出
? F:战车保持方向向右,移动 $1$ 个单位到达 $(1, 0)$。方向仍为向右,速度 $V$ 变为 $2$。 - 评测机输入
5:$(1, 0)$ 到 $(1, 5)$ 的距离为 $5$。 - 玩家输出
? L:战车向左旋转 90 度(方向变为向上),移动 $2$ 个单位到达 $(1, 2)$。方向为向上,速度 $V$ 变为 $3$。 - 评测机输入
3:$(1, 2)$ 到 $(1, 5)$ 的距离为 $3$。 - 玩家输出
? F:战车保持方向向上,移动 $3$ 个单位到达 $(1, 5)$。方向为向上,速度 $V$ 变为 $4$。 - 评测机输入
0:到达神庙,交互成功结束。