P17055 [NWERC 2022] 原地打转 / Going in Circles

译自 [Northwestern Europe Regional Contest (NWERC) 2022](https://2022.nwerc.eu) Problem G。 原题许可协议为 CC BY-SA。

世界闻名的侦探 Hercule Poirot 正在 Disorient Express 上自己的车厢里惬意地喝茶，这时列车长急匆匆地冲了进来。 “我们已经弄不清火车有多少节车厢了！”列车长喊道。 你看，这不是一列普通的火车，它既没有第一节车厢，也没有最后一节车厢。相反，所有车厢被连接成了一个大环，这正是列车长困惑的原因。 Hercule 思考了一会儿。“这真是很奇怪，”他说，“但我也许能帮上忙。”他伸手拿起旁边桌上的台灯。“你看，每节车厢都有一个像这样的灯开关。通过在车厢之间移动并拨动这些开关，我们可以确定车厢数量。” 列车长有些怀疑，但同意试试看。“我们很赶时间，”他说，“所以请在最多 $3n+500$ 步内确定 $n$，也就是这列火车包含的车厢数。”这里的一步指的是移动到相邻车厢，或者拨动当前车厢的灯开关。“我唯一确定的是，$n$ 至少为 $3$，至多为 $5000$。” ## 交互方式 这是一道交互题。你的程序会与一个交互器一起运行。交互器读取你程序的标准输出，并向你程序的标准输入写入内容。交互必须遵循以下协议。 交互器首先发送一个整数 $s$（$s \in \{0,1\}$），表示 Hercule 初始所在车厢的灯开关状态。 随后，你的程序最多可以发送 $3n+500$ 个让 Hercule 执行的步骤。注意，这里的 $n$ 是当前测试点中真实的车厢数量，而不是可能的最大车厢数量。每个步骤输出一行，格式为 `? a`，其中 $a$ 是以下三种之一： - `left`：移动到顺时针方向的相邻车厢； - `right`：移动到逆时针方向的相邻车厢； - `flip`：拨动当前车厢的灯开关。 每一步之后，交互器都会回复一个整数 $s$（$s \in \{0,1\}$），表示 Hercule 执行请求步骤后当前所在车厢的灯开关状态。 当你确定车厢数量 $n$ 后，输出一行 `! n`（$3 \leq n \leq 5000$），随后交互停止。输出答案不计入查询次数。 交互器不是自适应的；灯开关的初始状态在任何交互发生之前就已经由交互器确定。每次写入后请确保刷新缓冲区。使用超过 $3n+500$ 次查询会得到错误答案。 题包提供了一个测试工具帮助你开发程序。

本题为交互题。交互器初始向程序发送一个整数 $s$，表示初始车厢灯开关状态。

你的程序按照交互协议输出查询 `? left`、`? right`、`? flip`，并最终输出 `! n`。

【数据规模与约定】 对于所有数据，满足 $3 \leq n \leq 5000$；初始灯状态 $s \in \{0,1\}$；最多允许 $3n+500$ 次步骤查询。