P16396 [ECUSTPC 2026 Spring] Left Light, Right Walk.

:::epigraph I love you in a way. :::

**This problem shares the same background as Problem E “Right Light, Left Walk”. The two problems are closely related, so it is recommended to read the other problem’s statement before attempting either one.** **This is an interactive problem.** Little T is puzzled by the metro map of City T... Specifically, the city lies on both sides of the E River. On the north bank there are $n$ metro stations $N_1, N_2, \dots, N_n$, and on the south bank there are $n$ metro stations $S_1, S_2, \dots, S_n$. City T has a total of $n-1$ metro lines. Each line is a loop line. For the $i$-th loop line, the stations it connects are $N_i - N_{i+1} - S_{i+1} - S_i - N_i$. However, these loop lines are all one-way. The direction may be $N_i \leftarrow N_{i+1} \leftarrow S_{i+1} \leftarrow S_i \leftarrow N_i$, or it may be $N_i \to N_{i+1} \to S_{i+1} \to S_i \to N_i$. Each loop line has a price list $u_i, d_i, l_i, r_i$, representing the cost of riding one stop between the following 4 pairs of adjacent stations: ($N_i - N_{i+1}$, $S_i - S_{i+1}$, $N_i - S_i$, and $N_{i+1} - S_{i+1}$). Note that the travel direction for riding one stop is determined by the operating direction of the loop line; it could be $N_i \to N_{i+1}$ or $N_i \leftarrow N_{i+1}$. Unfortunately, a spacetime black hole has swallowed both the operating directions and the prices on the price lists. Little T plans to ask Big K for help to find out the operating direction of each metro line. Big K knows the operating directions. However, for each loop line, Little T may arbitrarily assign a new set of prices for its four adjacent edges. Big K knows the true operating directions, and will answer Little T’s queries based on these assigned prices. Little T may ask at most $3500$ questions: - From station $x$ (it can be $N_i$ or $S_i$, same below) to station $y$, riding the metro under the fare table assigned by Little T, what is the minimum metro cost that must be paid? - If different loop lines connect the same pair of adjacent stations, then all those edges exist simultaneously and can all be used. The cost of one trip is the sum of the weights of the edges traveled, and transfers at stations have no extra cost. After asking these questions, Little T must confirm with Big K the operating direction of each metro line. Please help Little T solve this problem. Note that the directions of the metro lines are predetermined and will not change during the interaction. In other words, the interactor is **not** adaptive. ### Interaction Protocol For each test point, there is only one set of testdata. The first line contains an integer $n \ (2 \le n \le 10^5)$, indicating the parameter. There are $2n$ stations in total and $n-1$ loop lines in total. You must first output $n-1$ lines. In the $i$-th line, output 4 integers $u_i, d_i, l_i, r_i$, representing the movement costs between the 4 pairs of adjacent stations on the $i$-th loop line: $N_i - N_{i+1}$, $S_i - S_{i+1}$, $N_i - S_i$, and $N_{i+1} - S_{i+1}$. You must guarantee that these four integers are in $[0, 10^9]$. Then the interaction starts immediately. In each interaction, you may ask the interactor a question in the following format: - Output one line. First output a character `?` to indicate a query, then output 4 elements $S_x, id_x, S_y, id_y$. You must ensure that $S_x, S_y \in \{\texttt{N}, \texttt{S}\}$ and $id_x, id_y \in \{m \in \mathbb{N} : 1 \le m \le n\}$. This means Little T asks Big K: from the $id_x$-th station on bank $S_x$, i.e. $(S_x)_{id_x}$, to the $id_y$-th station on bank $S_y$, i.e. $(S_y)_{id_y}$, what is the minimum metro cost that must be paid. - If your query is valid and you have not exceeded the query limit, the interactor will output one line containing an integer $d$, representing the minimum metro cost between the two stations. - If you exceed the corresponding query limit, the interactor will output an integer $-1$ and terminate your interaction process. In this case, you will receive a Wrong Answer verdict. If you have determined the metro directions, output the answer in the following format: - Output one line. First output a character `!`, then output a string $S$ of length $n-1$. The $i$-th character $S_i \in \{\texttt{I}, \texttt{O}\}$. If $S_i = \texttt{I}$, it means the direction of the $i$-th loop line is $N_i \leftarrow N_{i+1} \leftarrow S_{i+1} \leftarrow S_i \leftarrow N_i$. If $S_i = \texttt{O}$, it means the direction of the $i$-th loop line is $N_i \to N_{i+1} \to S_{i+1} \to S_i \to N_i$. After outputting the answer, you should exit safely. Each output must end with a newline and flush the buffer, otherwise you may get unexpected results. To flush the buffer, you can: - For C or C++, use `fflush(stdout)` or `cout.flush()`. - For Java or Kotlin, use `System.out.flush()`. - For Python, use `stdout.flush()`.

N/A

N/A

### Explanation for Sample 1 :::align{center}  ::: The figure above shows the operating directions of the metro and Little T’s price markings. Note that the interactive process in the sample is for reference only. The actual interactive process is not unique, and this example’s interactive process may not be feasible or optimal. The sample for this problem will not appear in the additional files. Translated by ChatGPT 5