P16396 [ECUSTPC 2026 Spring] 左灯右行

:::epigraph 我爱你有种 :::

**本题和试题 E 右灯左行共用相同的背景，两道题之间有较大的关系，建议在尝试其中一题前首先阅读另一题的文本。** **这是一道交互题。** 小 T 面对 T 城的地铁图犯了难…… 具体而言，这座城市在 E 河两岸，北岸有 $n$ 个地铁站点 $N_1, N_2, \dots, N_n$，南岸有 $n$ 个地铁站点 $S_1, S_2, \dots, S_n$。 T 城总共有 $n-1$ 条地铁线路，每条线路都是环线，其中第 $i$ 条环线连接的地铁站是 $N_i - N_{i+1} - S_{i+1} - S_i - N_i$，但这些地铁环线都是单向运行的，可能是 $N_i \leftarrow N_{i+1} \leftarrow S_{i+1} \leftarrow S_i \leftarrow N_i$ 也可能是 $N_i \to N_{i+1} \to S_{i+1} \to S_i \to N_i$。 每条环线都有一个价目表 $u_i, d_i, l_i, r_i$，分别表示这 4 个相邻站（$N_i - N_{i+1}$, $S_i - S_{i+1}$, $N_i - S_i$ 和 $N_{i+1} - S_{i+1}$）之间坐一站地铁移动的价格，注意坐一站地铁的方向由地铁的运行方向而定，可能是 $N_i \to N_{i+1}$ 也可能是 $N_i \leftarrow N_{i+1}$。 遗憾的是，时空黑洞吞噬了价目表上这些环线的运行方向和价格，小 T 准备求助大 K 的帮助来得知这些地铁的运行方向。 大 K 知道地铁的运行方向，不过，小 T 可以为每条环线的四段相邻站边重新任意指定一组价格；大 K 知道真实的运行方向，并会根据这些指定价格回答小 T 的询问。 小 T 可以询问他至多 $3500$ 个问题： - 地铁站 $x$（可以是 $N_i$ 也可以是 $S_i$，下略）到地铁站 $y$ 坐地铁，在小 T 指定的地铁价目表下，至少需要支付多少地铁费用？ - 若不同环线连接同一对相邻站，则这些边同时存在并且都可以使用。一次旅行的费用为所经过边权之和，站点间换乘不额外收费。 在询问完这些问题后，小 T 需要和大 K 确认每条地铁的运行方向。 请帮助小 T 解决这个问题。 请注意，地铁线路的方向是预先确定的，它们不会在交互的过程中更改，换言之交互器 **不是** 自适应的。 ### 交互协议 本题每个测试点只有一组测试数据。 第一行输入一个整数 $n \ (2 \le n \le 10^5)$，表示参数，其中地铁站共 $2n$ 座，环线共 $n-1$ 条。 你首先需要输出 $n-1$ 行，其中第 $i$ 行输出 4 个整数 $u_i, d_i, l_i, r_i$，分别表示第 $i$ 条环线上 $N_i - N_{i+1}$, $S_i - S_{i+1}$, $N_i - S_i$ 和 $N_{i+1} - S_{i+1}$ 这四个相邻站之间的移动价格，你需要保证这四个整数在 $[0, 10^9]$ 之间。 随后你将会直接开始交互，每一次交互你可以以下面的格式向交互器询问问题： - 输出一行，首先输出一个字符 `?` 表示你询问一次，随后输出 4 个元素 $S_x, id_x, S_y, id_y$，其中你需要保证 $S_x, S_y \in \{\texttt{N}, \texttt{S}\}$, $id_x, id_y \in \{m \in \mathbb{N} : 1 \le m \le n\}$，表示小 T 需要询问大 K 位于 $S_x$ 岸的第 $id_x$ 个地铁站 $(S_x)_{id_x}$ 到位于 $S_y$ 岸的第 $id_y$ 个地铁站 $(S_y)_{id_y}$ 之间至少需要支付多少地铁费用。 - 若你的输入合法并且没有超出询问限制，交互器会给出一行一个整数 $d$ 供输入表示这两个站点之间最少需要的地铁费用。 - 若你询问的问题超出了对应的询问次数限制，交互器会输出一个整数 $-1$ 并结束你的交互进程，此时你会获得答案错误的评测结果。 若你已经得到地铁方向的话，请按照以下的格式输出答案： - 输出一行，首先输出一个字符 `!`，随后输出一个长度为 $n-1$ 的字符串 $S$，其中第 $i$ 个字符 $S_i \in \{\texttt{I}, \texttt{O}\}$，若 $S_i = \texttt{I}$ 则表示第 $i$ 条环线的方向为 $N_i \leftarrow N_{i+1} \leftarrow S_{i+1} \leftarrow S_i \leftarrow N_i$，若 $S_i = \texttt{O}$ 则表示第 $i$ 条环线的方向为 $N_i \to N_{i+1} \to S_{i+1} \to S_i \to N_i$。 在完成输出答案后，你应当安全退出。 每次输出都需要输出换行并且刷新缓冲区，否则你可能会得到意料之外的结果。 为了刷新缓冲区，你可以： - 对于 C 或者 C++，使用 `fflush(stdout)` 或 `cout.flush()`。 - 对于 Java 或 Kotlin，使用 `System.out.flush()`。 - 对于 Python，使用 `stdout.flush()`。

无

无

### 样例 1 解释 :::align{center}  ::: 上面的图展示了地铁的运行方向和小 T 的价格标注。 请注意样例中的交互过程仅供参考，实际交互过程并不唯一，且这一示例的交互过程不一定是可行的或是最优的，本题的样例不会在附加文件中出现。