This problem shares the same background as Problem E Right & Left, and the two problems are closely related. It is recommended to read the text of the other problem first before attempting either of them.

This is an interactive problem.

Little T is having trouble with the subway map of City T...

Specifically, this city is located on both sides of River E. The north bank has $$$n$$$ subway stations $$$N_1$$$, $$$N_2$$$, $$$\ldots$$$, $$$N_n$$$, and the south bank has $$$n$$$ subway stations $$$S_1$$$, $$$S_2$$$, $$$\ldots$$$, $$$S_n$$$.

City T has a total of $$$n - 1$$$ subway lines, each of which is a loop line. The $$$i$$$-th loop line connects the subway stations $$$N_i - N_{i + 1} - S_{i + 1} - S_i - N_i$$$. However, these subway loop lines operate in a single direction. It might be $$$N_i \leftarrow N_{i + 1} \leftarrow S_{i + 1} \leftarrow S_i \leftarrow N_i$$$ or $$$N_i \rightarrow N_{i + 1} \rightarrow S_{i + 1} \rightarrow S_i \rightarrow N_i$$$.

Each loop line has a price list $$$u_i$$$, $$$d_i$$$, $$$l_i$$$, $$$r_i$$$, respectively representing the price of traveling one subway station between the 4 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 direction of traveling one subway station depends on the operating direction of the subway, which might be $$$N_i \rightarrow N_{i + 1}$$$ or $$$N_{i} \leftarrow N_{i + 1}$$$.

Unfortunately, a space-time black hole swallowed the operating directions and prices of these loop lines on the price list. Little T plans to seek Big K's help to find out the operating directions of these subways.

Big K knows the true operating directions of the subways. However, Little T can arbitrarily re-assign a set of prices for the four adjacent station edges of each loop line; Big K will answer Little T's queries based on these assigned prices.

Little T can ask him up to $$$3\,500$$$ questions:

• How much subway fare must be paid at least to travel from subway station $$$x$$$ (can be $$$N_i$$$ or $$$S_i$$$, same below) to subway station $$$y$$$ under the subway price list assigned by Little T?
• If different loop lines connect the same pair of adjacent stations, these edges exist simultaneously and can all be used. The cost of a trip is the sum of the weights of the edges passed, and there is no extra charge for transfers between stations.

After asking these questions, Little T needs to confirm the operating direction of each subway line with Big K.

Please help Little T solve this problem.

Please note that the directions of the subway lines are predetermined and they will not change during the interaction process. In other words, the interactor is not adaptive.

Each test case in this problem contains only one set of test data.

The first line of input contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$), representing the parameter, where there are $$$2n$$$ subway stations and $$$n - 1$$$ loop lines in total.

You first need to output $$$n - 1$$$ lines, where the $$$i$$$-th line outputs $$$4$$$ integers $$$u_i$$$, $$$d_i$$$, $$$l_i$$$, $$$r_i$$$, respectively representing the moving prices between the four adjacent stations $$$N_i - N_{i + 1}$$$, $$$S_i - S_{i + 1}$$$, $$$N_i - S_i$$$, and $$$N_{i + 1} - S_{i + 1}$$$ on the $$$i$$$-th loop line. You need to ensure that these four integers are between $$$[0, 10^9]$$$.

Then you will directly start the interaction. For each interaction, you can ask the interactor questions in the following format:

• Output a line. First, output a character ? indicating you are making a query. Then output $$$4$$$ elements $$$S_x$$$, $$$id_x$$$, $$$S_y$$$, $$$id_y$$$, where you need to ensure $$$S_x, S_y \in \{\mathtt{N}, \mathtt{S}\}$$$, $$$id_x, id_y \in \{m \in \mathbb{N} : 1 \le m \le n\}$$$. This means Little T needs to ask Big K how much subway fare must be paid at least between the $$$id_x$$$-th subway station $$$(S_x)_{id_x}$$$ located on the $$$S_x$$$ bank and the $$$id_y$$$-th subway station $$$(S_y)_{id_y}$$$ located on the $$$S_y$$$ bank.
• If your input is valid and does not exceed the query limit, the interactor will provide a line with a single integer $$$d$$$ to input, representing the minimum required subway fare between these two stations.
• If the question you asked exceeds the corresponding query limit, the interactor will output an integer $$$-1$$$ and terminate your interaction process. At this point, you will receive a Wrong Answer verdict.

If you have already obtained the subway directions, please output the answer in the following format:

• Output a line. First, output a character !. Then output a string $$$S$$$ of length $$$n - 1$$$, where the $$$i$$$-th character $$$S_i \in \{\mathtt{I}, \mathtt{O}\}$$$. If $$$S_i = \mathtt{I}$$$, it indicates 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 = \mathtt{O}$$$, it indicates the direction of the $$$i$$$-th loop line is $$$N_i \rightarrow N_{i + 1} \rightarrow S_{i + 1} \rightarrow S_i \rightarrow N_i$$$.

After completing the output of the answer, you should exit safely.

Every output needs to include a newline and flush the buffer, otherwise you might 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().