Today, oToToT received two convex polygons, denoted as $$$A$$$ and $$$B$$$, as his toys. After playing with them for a while, oToToT accidentally dropped the convex polygon $$$B$$$ into a puddle of paint! As a result, any area covered by convex polygon $$$B$$$ will be colored.

Being an enthusiastic competitive programmer, oToToT immediately came up with a question: If convex polygon $$$B$$$ is translated (no rotation allowed) inside convex polygon $$$A$$$, what is the area that is possible to be colored by convex polygon $$$B$$$?

However, oToToT recently encountered a dreadful 3D geometry problem, Codeforces 102452F, hence doesn't want to touch any computational geometry problem recently. Therefore, he entrusts you, who is forced to participate in this contest, to help solve the problem.

Note: We say convex polygon $$$B$$$ is inside convex polygon $$$A$$$ when all points of convex polygon $$$B$$$ lie within convex polygon $$$A$$$.

This is an interactive problem.

There is an array $$$[a_1, a_2, \ldots, a_N]$$$ initialized with a secret permutation of size $$$N = 100$$$.

Formally speaking, $$$\begin{cases}a_i \in \mathbb{N}, &\forall i = 1, 2, \ldots, N\\1 \leq a_i \leq N, &\forall i = 1, 2, \ldots, N\\ a_i \neq a_j, &\forall i \neq j \end{cases}$$$.

You are asked to sort it in ascending order within $$$50000$$$ operations. In each operation, you can perform any one of the following actions:

• Pick a consecutive subarray of size at least $$$5$$$ and randomly shuffle it.
• Query the $$$k$$$-th smallest value of $$$|a_i - i|$$$ for $$$i = 1, 2, \ldots, N$$$.
• Claim that the array has been sorted.

Can you do it?

The interaction begins without reading anything such as $$$N$$$. To perform an operation, please output a line:

• # l r: Shuffle the interval $$$a[l..r]$$$. $$$l, r$$$ should satisfy $$$1 \leq l \leq r \leq 100$$$ and $$$r - l + 1 \geq 5$$$. After calling this operation, the judge shuffles $$$[a_l, a_{l + 1}, \ldots, a_r]$$$ randomly. That is, each possible $$$(r - l + 1)!$$$ permutations is equiprobably produced. After that, you should read a single integer $$$v$$$ written on a separate line. $$$v = 0$$$ if the shuffle action is successfully executed. Otherwise, you might have made an incorrect shuffle request; in this case, your program should terminate immediately to avoid undefined behavior.
• ? k: Query the $$$k$$$-th smallest value of $$$|a_i - i|$$$ for $$$i = 1, 2, \ldots, N$$$. $$$k$$$ should satisfy $$$1 \leq k \leq N$$$. After that, you should read an integer $$$b$$$, the query result. If $$$b = -1$$$, you might have made an invalid query; in this case, your program should terminate immediately to avoid undefined behavior. Otherwise, $$$b$$$ is the value you asked for.
• !: Claim that the array has been sorted. Once choosing this action, the judge takes a look on the current array to see if it is really sorted and gives you a verdict accrodingly. Your program should terminate immediately after calling this operation. Please note that this is also counted as an operation so it cannot be made on the $$$50001$$$-th move.

• fflush(stdout) in C;
• fflush(stdout) or cout.flush() in C++;
• stdout.flush() in Python;

One day, Edisonhello, YP, and Baluteshih were testing a programming contest named PDAO. After reading problem A, Edisonhello conceptualized it and explained what to do to their main coder, YP. However, due to a communication problem, YP misinterpreted the description, resulting in an incorrect understanding. As YP found the misunderstood version of the problem difficult enough (and he did not want to waste any piece of code written), he would like to include it as one of the problems in the 2023 NTU ICPC Team Preliminary.

The intended version of the problem in PDAO was:

Given an integer $$$N$$$, for each $$$k = 1, 2, \ldots, N$$$, output

$$$$$$ \max_{(A, B) \in \wp(N, k)} \dfrac{f(A, B)}{\displaystyle \prod_{i = 1}^{k} p_i} $$$$$$

where $$$\wp(N, k)$$$ collects all partitions $$$(A, B)$$$ of $$$S = \{1, 2, \ldots, N\}$$$ such that $$$\begin{cases} A \cap B = \emptyset \\ A \cup B = S \\ |B| = k\end{cases}$$$, $$$f(A, B)$$$ denotes the cardinality of the set $$$\{(a, b) \mid (b \equiv 0 \mod a) \wedge (a, b) \in A \times B\}$$$, and $$$p_i$$$ denotes the $$$i$$$-th smallest prime number (e.g., $$$p_1 = 2, p_2 = 3, p_3 = 5$$$).

YP misunderstood the definition of the denominator in the expression. So the problem you need to solve is instead:

Given an integer $$$N$$$, for each $$$k = 1, 2, \ldots, N$$$, output

$$$$$$ \max_{(A, B) \in \wp(N, k)} \dfrac{f(A, B)}{\displaystyle \prod_{b \in B} b} $$$$$$

where the definition of $$$\wp$$$ and $$$f$$$ remains the same.

Dinner time! oToToT is looking for a good restaurant, but he has been overwhelmed by the amount of choice. There are $$$n\ (1 \le n \le 3\cdot 10^5)$$$ restaurants and $$$n$$$ types of dishes in the city. The $$$i$$$-th restaurant serves the $$$a_i$$$-th type of dish. Now, oToToT is curious about a question:

"If he walks from the $$$x$$$-th restaurant to the $$$y$$$-th restaurant, is the $$$k$$$-th dish an appropriate choice?"

Since route planning can be exhausting, oToToT has filtered out some redundant streets to ensure that there are exactly one path between any two restaurants; the streets preserved by oToToT form an undirected tree. oToToT answers the question with the following method:

1. Initially, the $$$k$$$-th dish is believed appropriate.
2. oToToT moves from the $$$x$$$-th restaurant to the $$$y$$$-th restaurant.
3. Whenever oToToT reaches a restaurant (including the $$$x$$$-th and the $$$y$$$-th restaurant) that serves the $$$k$$$-th dish, he simply changes his opinion.
4. oToToT confirms his answer after he reaches the $$$y$$$-th restaurant. There's an exception: if the $$$k$$$-th dish is not served at any of the restaurants on the path, it cannot be appropriate.

oToToT also wants to know the number of appropriate dishes, but he is too tired to solve the problem by himself. oToToT will list $$$q\ (1 \le q \le 3\cdot 10^5)$$$ pairs of $$$(x_i, y_i)$$$. Help him count the number of appropriate dishes between the $$$x_i$$$-th restaurant and the $$$y_i$$$-th restaurant. You must figure out the answer before the next query arrives.

Urgent!!

The two great legends, Tseng and Chou, are debating the pronunciation of "Er Wei Shu Dian." You need to stop their quarrel in time; otherwise, the world would be diminished due to the disorder of the two great powers. In order to stand out from them, you must solve this variant of the classic "Er Wei Shu Dian" problem first.

Now, you are given $$$N$$$ points, the $$$i$$$-th point can be described by two integers ($$$x_i$$$, $$$y_i$$$), which means that the $$$i$$$-th point is placed at ($$$x_i$$$, $$$y_i$$$) on a 2D plane. For the $$$i$$$-th point, you need to find out how many points are strictly inside the upper-left corner and the upper-right corner. Since this is an urgent task, to save your time, you only need to output the sum of these values.

This is a problem from a story about misreading the problem statement and coming up with a (fake) solution.

Consider a sequence of $$$N$$$ non-negative integers $$$a_1, \dots, a_N$$$. A single operation consists of the following 3 steps:

1. Choose any index $$$1 \leq i \leq N$$$.
2. Choose any non-negative integer $$$j$$$ such that $$$2^j \leq a_i$$$.
3. Change $$$a_i$$$ to $$$a_i \mathbin{|} (a_i - 2^j)$$$. Here, $$$-$$$ denotes natural subtraction, and $$$\mathbin{|}$$$ denotes bitwise-or.

Your goal is to make the bitwise-or of the whole sequence as big as possible by performing zero or more operations. You also need to solve the minimum number of operations to obtain the maximum bitwise-or.

In the NTU field, there are $$$N$$$ people standing on a land shaped like a number line, waiting to participate in the unique NTU game. Each person can be considered to be standing at coordinate $$$x_i$$$ on the number line.

As the game master of the event, you need to group these people. For each group, let $$$l$$$ be the minimum coordinate, and $$$r$$$ be the maximum coordinate among the people in the group. Then, you have to pay $$$a + b\times(r - l)$$$ dollars to organize a game for that group.

You quickly realize how to minimize the cost of grouping everyone efficiently. However, you soon discover that the cost is still very high. To address this, you wish to dismiss some people to reduce the overall cost of the game.

After conducting some investigations, you find out that asking the $$$i$$$-th person to leave requires spending $$$c_i$$$ dollars. Moreover, there are $$$M$$$ hidden friend relations among these people. Each friend relation is represented as a triple $$$(u_i, v_i, w_i)$$$, which means there is a friendship between $$$u_i$$$ and $$$v_i$$$. If exactly one person among $$$u$$$ and $$$v$$$ is asked to leave, you will need to spend an additional $$$w_i$$$ dollars to compensate for their friendship!

Despite the complexity of these relationships, you still aim to minimize the total cost of the game. Please write a program that takes the given input and outputs the minimum possible cost.

A Suica Graph is defined as an undirected graph that can be constructed using the following procedures.

1. Start with an empty graph (with no vertices or edges).
2. Add a head vertex $$$H$$$.
3. Add a tail vertex $$$T$$$.
4. Add $$$N$$$ stripe chains $$$C_1, C_2, \dots, C_N$$$. Each chain is a set of degree-2 vertices. When adding chain $$$C_i$$$, we first add $$$l_i$$$ vertices, say $$$v_1, v_2, \dots, v_{l_i}$$$. Then add edges between adjacent vertices; i.e., for all $$$1 \leq j \lt l_i$$$, add edges between $$$v_j$$$ and $$$v_{j+1}$$$. Finally, add two edges $$$\{H, v_1\}$$$ and $$$\{v_{l_i}, T\}$$$.
5. Add the stem chain. Suppose that the length of the stem chain is $$$S$$$, then add $$$S$$$ vertices denoted by $$$u_1, u_2, \dots, u_S$$$. Secondly, add edges between adjacent vertices; i.e., for all $$$1 \leq j \lt S$$$, add edges between $$$u_j$$$ and $$$u_{j+1}$$$. Finally, add edge $$$\{H, u_1\}$$$.

Here are some examples of Suica Graphs:

You are given a Suica Graph. For each vertex, you can color it red or blue. Please count how many different Harmony colorings there are. Since the answer could be large, you only need to output the remainder of the answer modulo by $$$998244353$$$.

A coloring is called Harmony if and only if:

1. There is at least one red vertex and at least one blue vertex.
2. For each pair of red vertices $$$(x, y)$$$, $$$x$$$ can reach $$$y$$$ through some edges without touching blue vertices.
3. For each pair of blue vertices $$$(x, y)$$$, $$$x$$$ can reach $$$y$$$ through some edges without touching red vertices.

In other words, a coloring is Harmony if and only if the induced subgraph of red vertices is connected, the induced subgraph of blue vertices is connected, and both of them are not empty graphs (i.e., having at least one vertex).

Two coloring ways are considered different if and only if there exists a vertex colored differently in the two coloring ways.

The section below is from IMO 2023 problem 5.

Let $$$n$$$ be a positive integer. A Japanese triangle consists of $$$1 + 2 + \cdots + n$$$ circles arranged in an equilateral triangular shape such that for each $$$i = 1, 2, \ldots , n$$$, the (i)-th row contains exactly $$$i$$$ circles, exactly one of which is coloured red. A ninja path in a Japanese triangle is a sequence of $$$n$$$ circles obtained by starting in the top row, then repeatedly going from a circle to one of the two circles immediately below it and finishing in the bottom row. Here is an example of a Japanese triangle with $$$n = 6$$$, along with a ninja path in that triangle containing two red circles.

Note that this is not the ninja path containing maximum red circles.

Now, you are given a configuration of a Japanese triangle, please find the ninja path containing maximum red circles.

The only differences between this problem and More Japanese Monsters are Input and Output.

The great player Rgnerd is playing a well-known Japanese game called Pekomon. In this game, he will encounter many different Peko Monsters. He can either capture the Peko Monster he meets or decide to kill it directly. Each Peko Monster has different skills, and some of them are considered legendary due to their high-level skills.

One day, Rgnerd bumped into a legendary Peko Monster, Splash Splash Rage Shark. Even though Splash Splash Rage Shark is a legendary Peko Monster, Rgnerd still thinks it is pretty easy to defeat it.

One of the skills of Splash Splash Rage Shark is to metamorphose. After the metamorphosis, Splash Splash Rage Shark will hide in a string $$$S$$$. Rgnerd knows that if Splash Splash Rage Shark does exist in that string, it must be in one of the suffixes of the string. Similar to the abbreviation of Splash Splash Rage Shark's form, Rgnerd also identifies that it must be hidden in the form of $$$AABA$$$, where $$$A$$$ and $$$B$$$ are some non-empty strings.

To demonstrate how easily Rgnerd can kill Splash Splash Rage Shark, he will showcase his quantum sword skill. He will kill all possible Splash Splash Rage Sharks at the same time. You want to know how many possible kinds of Splash Splash Rage Sharks are killed by Rgnerd at the same time.

Formally, given a string $$$S$$$, for each suffix $$$\text{Suf}_i=S_{i\dots |S|}$$$, you need to find out how many possible ways $$$\text{Suf}_i$$$ can be decomposed into the form of $$$AABA$$$. We will denote this number as $$$A_i$$$.

Here comes a well-known problem,

This problem has appeared in various online judges, including TIOJ 1905, Codeforces 765F, Codeforces 1793F, and even CS Academy Closest Numbers. Why do we still need to solve this problem?

Let us present an advanced version of it. In this version, we provide $$$Q$$$ queries for a given integer sequence $$$a_1, a_2, \ldots, a_N$$$, where each query asks to find the second smallest value among the absolute differences of all pairs of elements within a specified range $$$[l_i, r_i]$$$.

In this context, the second smallest value within a multiset $$$S$$$ is determined as the minimum value $$$v$$$, for which there are at least two elements in $$$S$$$ that are not greater than $$$v$$$.

NTU Factory recently received $$$N$$$ orders, each containing the following information:

1. The final item to be produced.
2. The earliest start time. For example, the required materials for the final item may arrive at a certain time.
3. The expected deadline $$$d_i$$$.

To complete each final item, the factory needs to go through multiple works. These works cannot be parallelized; that is, the $$$(i + 1)$$$-th work can only start after the $$$i$$$-th work is done. More precisely, each order is divided into $$$k_i$$$ works $$$w_{i, 1}, w_{i, 2}, \ldots, w_{i, k_i}$$$, representing the $$$k_i$$$ works within the order. For each work $$$a$$$, there is an item $$$z_a$$$ required to be produced. Once all these $$$k_i$$$ works are done, the final item is then magically produced.

To maintain the responsiblility of each factory labor, there are certain constraints when multiple works aim to produce the same item:

1. These works cannot be performed simultaneously; one must be completed before the other starts.
2. To determine which work should be done earlier, the labors should follow the following rule. Recall that each work belongs to an order, right? A work belonging to an order with earlier deadline should be done first. That is, if we focus on all the works producing a specific item $$$z$$$ and sort these works in chronological order of their completion time, it should have also been sorted by the deadlines of their belonging order.

To complete the numerous works, the factory needs $$$M$$$ resources. For each resource, the factory must assign a production sequence, specifying the order of works in which each resource should process. These assigned production sequences form a production plan. Once the production plan is determined, each resource starts processing works according to its assigned sequence. However, if a resource finds that the next work it needs to process depends on other works that have not been completed, the resource will pause until all dependencies are resolved before continuing.

Currently, NTU Factory's production plan is manually determined, but the existing method, though free from sequence conflicts, is highly inefficient, leading to many delayed orders. To improve production efficiency, the NTU Factory owner asks the engineers to use programming techniques to optimize the production plan.

The engineer has come up with the following method: Define a state as the production sequence for each resource. The initial state can be obtained from the current production plan. After obtaining the initial state, the following improvements are repeatedly carried out:

• Step 1. Select a continuous segment of works on one resource.
• Step 2. Attempt to insert this continuous segment of works into the production sequence of a certain resource (which can be the same resource).
• Step 3. Temporarily store the new state as a test production plan and evaluate whether to accept this new state based on production efficiency, the number of delayed orders, and other evaluation metrics. The new state will not be adopted if it performs poorly.

The current issue faced by the engineer is that Step 2 may lead to conflicts in the work sequence. For example, the production plan may cause two resources to wait for each other's works to be completed, resulting in both resources pausing and not processing any works.

Therefore, the engineer entrusts you with the task of implementing a procedure that can input the current production plan, select a continuous segment of works in Step 1, and then repeatedly answer whether conflicts will occur in the work sequence after attempting to insert this segment of works into a specified new position in Step 2.

The only differences between this problem and Japanese Monsters are Input and Output.

The great player Rgnerd is playing a well-known Japanese game called Pekomon. In this game, he will encounter many different Peko Monsters. He can either capture the Peko Monster he meets or decide to kill it directly. Each Peko Monster has different skills, and some of them are considered legendary due to their high-level skills.

One day, Rgnerd bumped into a legendary Peko Monster, Splash Splash Rage Shark. Even though Splash Splash Rage Shark is a legendary Peko Monster, Rgnerd still thinks it is pretty easy to defeat it.

One of the skills of Splash Splash Rage Shark is to metamorphose. After the metamorphosis, Splash Splash Rage Shark will hide in a string $$$S$$$. Rgnerd knows that if Splash Splash Rage Shark does exist in that string, it must be in one of the suffixes of the string. Similar to the abbreviation of Splash Splash Rage Shark's form, Rgnerd also identifies that it must be hidden in the form of $$$AABA$$$, where $$$A$$$ and $$$B$$$ are some non-empty strings.

To demonstrate how easily Rgnerd can kill Splash Splash Rage Shark, he will showcase his quantum sword skill. He will kill all possible Splash Splash Rage Sharks at the same time. You want to know how many possible kinds of Splash Splash Rage Sharks are killed by Rgnerd at the same time.

Formally, given a string $$$S$$$, for each suffix $$$\text{Suf}_i=S_{i\dots |S|}$$$, you need to find out how many possible ways $$$\text{Suf}_i$$$ can be decomposed into the form of $$$AABA$$$. We will denote this number as $$$A_i$$$.