背景

译自 Northwestern Europe Regional Contest (NWERC) 2022 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。

0
1
1
0
1
1
1
1

? right
? right
? right
? flip
? left
? left
? left
! 3

提示

【数据规模与约定】

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