A wonderful performance is about to begin on the stage set up by cold_beans...

The stage is a 2D Euclidean plane. Character A initially stands at the center of the stage, which is the origin $$$(0, 0)$$$. There are $$$n$$$ spotlights above the stage. Each spotlight projects a circular illuminated area on the plane with its center at $$$(x_i, y_i)$$$ and a radius of $$$\sqrt{x_i^2 + y_i^2}$$$. The boundary of the circle is included in the illuminated area.

To show the tension of the performance, A wants to always stay within the illuminated areas of all spotlights during the performance, and reach the farthest possible point from the center of the stage.

Please help A find the maximum distance from the center of the stage to a point she can reach under the above conditions.

Constructive Kingdom is still chasing Little T...

Define the prefix $$$\max$$$ sequence $$$x$$$ of a sequence $$$a$$$ of length $$$n$$$ as $$$x_i = \max\{a_j : 1 \le j \le i\}$$$, and the prefix $$$\min$$$ sequence $$$y$$$ as $$$y_i = \min\{a_j : 1 \le j \le i\}$$$.

Given $$$n$$$ and $$$k$$$, please construct two sequences $$$a$$$ and $$$b$$$, both of length $$$n$$$, that satisfy the following conditions. If no such two sequences exist, report that there is no solution:

• $$$a$$$ and $$$b$$$ are permutations of $$$1$$$ to $$$n$$$.
• $$$a$$$ and $$$b$$$ differ in at least one position, i.e., there exists an $$$i$$$ such that $$$a_i \ne b_i$$$.
• For each of $$$a$$$ and $$$b$$$, let its prefix $$$\max$$$ sequence be $$$x$$$ and its prefix $$$\min$$$ sequence be $$$y$$$. It must satisfy: $$$$$$ \sum_{i=1}^n (x_i - y_i) = k. $$$$$$

Pheonix has arrived in outer space. There are $$$n$$$ galaxies, numbered $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$n$$$. These galaxies are connected by $$$n - 1$$$ bidirectional wormhole channels, and any galaxy can be reached from any other galaxy via these wormholes.

Each galaxy contains some stars, and the number of stars in the $$$i$$$-th galaxy is $$$s_i$$$.

Pheonix will make $$$q$$$ wormhole trips between galaxies. During a single trip, Pheonix will not visit any galaxy more than once.

Pheonix has limited knowledge of astronomy, but his mathematical observation skills are keen. For each trip, he wants to ask Little T the following questions:

• Put the numbers of stars of the galaxies visited (including the starting and ending ones) during the wormhole trip from galaxy $$$x$$$ to galaxy $$$y$$$ into a multiset $$$S$$$, i.e., $$$S = \{s_i : i\ \text{is on the path from}\ x \ \text{to}\ y\}$$$.
• Are there any elements in $$$S$$$ whose frequency of occurrence is strictly greater than $$$\frac{|S|}{k}$$$? Here, $$$k$$$ is an integer specified by Pheonix in each query. If there are, find out what they are.

Please help Little T answer these questions.

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().

This problem shares the same background as Problem D Left & Right, 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 not 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}$$$.

Fortunately, a space-time white hole spat out the operating directions and prices of these loop lines on the price lists. Big K plans to seek Little T's help to get the prices for some subway trips.

As a person from another space-time, Big K will tell Little T the operating directions and price lists of these loop lines. Then Little T needs to answer $$$q$$$ questions:

• How much subway fare must be paid at least to travel by subway from city $$$x$$$ (can be $$$N_i$$$ or $$$S_i$$$, same below) to city $$$y$$$ under the given subway price list?

Please help Little T solve this problem.

Little T came to City T, and she is going to a Livehouse for a performance.

City T can be represented by an infinite Euclidean 2D plane. The positive direction of the $$$y$$$-axis represents due north (N), the positive direction of the $$$x$$$-axis represents due east (E), the negative direction of the $$$y$$$-axis represents due south (S), and the negative direction of the $$$x$$$-axis represents due west (W).

Little T is initially standing at position $$$(x_{t}, y_{t})$$$, initially facing one of the four directions: due east, south, west, or north. The Livehouse she wants to go to is located at $$$(x_l, y_l)$$$.

For each move, she can choose one of the following two options:

• Go straight, walk one unit length along the current direction.
• Turn right, rotate the direction Little T is facing by $$$90^\circ$$$ clockwise (North turns to East, East turns to South, South turns to West, West turns to North).
• Note that Little T cannot turn left or turn around.

Please calculate, under the above conditions, what is the minimum number of right turns Little T needs to make to reach the Livehouse.

This problem has no relation with Problem H Morrow by Morrow.

TSUCE (Time-Space Union of Coding Experts) is preparing to host the TSUCE Programming Duel Cup, an algorithmic programming 1v1 duel between two players!

The competition format is as follows. Please note the meanings of $$$n$$$ and $$$m$$$:

• Each match is played between two players.
• A match consists of a regular time + several overtime periods (possibly $$$0$$$ overtime periods). The regular time contains $$$2n$$$ rounds, and one overtime period contains $$$2m$$$ rounds. There is exactly one winner in a single round.
• The player who wins $$$n + 1$$$ rounds during regular time will win the whole match.
• If there is a tie after the $$$2n$$$ rounds of regular time (score $$$n:n$$$), the match will enter overtime. The player who wins $$$m + 1$$$ rounds in a single overtime period will win the whole match.
• If there is still a tie after one overtime period, the match will enter the next overtime period.
• The final score is the number of rounds won by each player.

Unfortunately, the scorekeeper Little T's database broke down. He only remembers the scores of all $$$k$$$ matches, but he forgot $$$n$$$ and $$$m$$$ related to the format.

Please help him determine whether there exists a valid pair of positive integers $$$n$$$ and $$$m$$$ such that all these scores are valid under this format.

This problem has no relation with Problem G CS:Go Over.

Little T is preparing some classic problems $$$\ldots$$$

Given a permutation $$$p = \{p_1, p_2, \ldots, p_n\}$$$ of length $$$n$$$, Little T will perform exactly one operation $$$(i, j)$$$:

• Choose a pair of indices $$$1 \le i \lt j \le n$$$, and swap $$$p_i$$$ and $$$p_j$$$ in $$$p$$$.

For all different valid operations $$$(i, j)$$$, Little T needs to calculate the sum of the orders of the permutations represented by the permutation after the swap.

Since the answer can be very large, Little T needs to calculate the answer modulo $$$998\,244\,353$$$.

Please help Little T calculate this problem.

The hints section of the problem provides related information about permutations.

Nailong is addicted to Stardew Valley during his holidays. To complete all achievements, he needs a lot of gold coins to purchase the Gold Clock, so he is currently in desperate need of gold coins.

In the game Stardew Valley, players can grow different crops. By growing crops, the player Nailong can earn the gold coins he needs.

It is now the morning of the $$$1$$$st day of Spring, and Spring lasts for $$$k$$$ days in total. Nailong has some arable plots of land, which are initially empty. He has $$$10^{10^{100}}$$$ gold coins on hand, and now he starts his farm work for the Spring.

Pierre's General Store sells $$$n$$$ types of single-harvest crop seeds and $$$m$$$ types of multi-harvest crop seeds. Their definitions are as follows:

• Single-harvest crop: the seed price is $$$p$$$ gold coins per unit, the selling price of the mature crop is $$$q$$$ gold coins per unit, and the maturation time is $$$t$$$ days. That is, a crop planted on day $$$i$$$ will become harvestable on day $$$i + t$$$. After harvesting, the crop will be removed, and the plot will become empty.
• Multi-harvest crop: the seed price is $$$p$$$ gold coins per unit, the selling price of the mature crop is $$$q$$$ gold coins per unit, and the maturation time is $$$t$$$ days. That is, a crop planted on day $$$i$$$ will become harvestable on day $$$i + t$$$. At the same time, this crop has a harvest cycle of $$$s$$$ days. After harvesting, the crop will not be removed, and a crop harvested on day $$$j$$$ will become harvestable again on day $$$j + s$$$.
• On day $$$k + 1$$$, Spring comes to an end and Summer arrives. All crops in the plots will wither and cannot be harvested, even if they were supposed to mature on that day.

Because Nailong is quite lazy, he will choose to plant at most one type of crop throughout the entire Spring.

Nailong can perform the following operations any number of times each day:

• Buy seeds from Pierre's General Store.
• Plant a unit of seed on an empty plot of land.
• Harvest a unit of crop that is in the "harvestable" state and sell it.
• Note that you cannot remove existing crops from the land unless it is a single-harvest crop being harvested.

Since all arable plots are equivalent, he wants to know the maximum profit in gold coins that each plot of land can bring him by the end of Spring.

Note that if it is impossible to make a profit no matter what, Nailong can choose to do nothing and gain a profit of $$$0$$$ gold coins by the end of Spring.

Nailong is killing monsters in the game. This is a turn-based game, and he encounters $$$n$$$ monsters with health points of $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ respectively.

Each turn, Nailong can cast one of the following skills once:

• Fireball: Select a monster, deal $$$x$$$ damage to it, and consume $$$a$$$ mana points.
• Flamestrike: Deal $$$y$$$ damage to all monsters, and consume $$$b$$$ mana points.

When a monster takes damage, an equal amount of health points will be deducted. If its health points are less than or equal to $$$0$$$, the monster will be killed. Nailong wins the battle when all $$$n$$$ monsters are killed.

Please help Nailong plan his skill usage to minimize the mana consumed while winning the battle, and calculate the minimum mana required.

Maddy is still purging Baddy's evil legion...

The game is played on an infinite Chinese Chess (Xiangqi) board, which is formed by the intersection of infinitely many horizontal and vertical lines. Each intersection can hold one chess piece. For ease of description, we abstract it as a 2D Cartesian coordinate system to represent the positions of the pieces.

Baddy controls $$$n$$$ black pawn pieces and one black general piece. These pieces are fixed at their initial positions during the game and will not move. The black pawns are deployed at the intersections $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, $$$\ldots$$$, $$$(x_n, y_n)$$$, and the black general is located at $$$(x_\text{K}, y_\text{K})$$$.

Now Maddy controls a red cannon piece. She can deploy the red cannon anywhere on the board. The red cannon follows the movement rules of Chinese Chess. Specifically:

• Move: Each move, it can travel any number of intersections along the horizontal or vertical line it is currently on. However, a single move must be strictly horizontal or strictly vertical; it cannot move in both directions at once. It cannot jump over other pieces on the same line during a normal move, nor can it capture a piece this way.
• Capture: It can choose an enemy piece on the same line (horizontal or vertical) as the target, but there must be exactly one piece (of any color) between them. After capturing, the cannon moves to the position of the captured enemy piece, and the captured piece is removed from the board.

After deploying the red cannon, Maddy can continuously make an infinite number of moves following the rules above.

Maddy now wants to know: is there a valid deployment strategy and a sequence of moves for the red cannon that can capture the black general? Please help her.

TSUCE's final exams are over! The grading teacher, Big K, looked at Little T's horrible exam paper.

Therefore, he decided to use the following tricks to save Little T, who scored $$$x$$$ points:

• Operation A, this trick can be used at most $$$a_1$$$ times. It takes the square root of Little T's current score $$$x$$$, multiplies it by 10, and rounds down, i.e., $$$x \leftarrow \lfloor 10 \sqrt{x} \rfloor$$$.
• Operation B, this trick can be used at most $$$a_2$$$ times. It multiplies Little T's current score $$$x$$$ by $$$0.7$$$, adds 30, and rounds down, i.e., $$$x \leftarrow \lfloor 0.7x + 30 \rfloor$$$.
• Operation C, this trick can be used at most $$$a_3$$$ times. It multiplies Little T's current score $$$x$$$ by $$$1.2$$$ and rounds down, i.e., $$$x \leftarrow \lfloor 1.2x \rfloor$$$.
• Operation D, this trick can be used at most $$$a_4$$$ times. It adds $$$5$$$ to Little T's current score $$$x$$$, i.e., $$$x \leftarrow x + 5$$$.

Please help Big K find a valid way to use these tricks so that Little T can obtain the maximum possible score.