Alice and Bob play a table tennis match under the 11-point system. Alice wins the match in the end. The rules for ending the match are as follows:

• If one player reaches $$$11$$$ points first and leads the opponent by at least $$$2$$$ points, the match ends immediately (e.g. $$$11:0$$$, $$$11:9$$$).
• If the score is tied at $$$10:10$$$, the match goes to deuce. After that, the match can only end when one player takes a lead of $$$2$$$ points (e.g. $$$12:10$$$, $$$13:11$$$).

You are given a rooted tree with $$$n$$$ nodes, where the root is node $$$1$$$. Each node of the tree is labeled with a lowercase English letter.

You need to count the number of valid 5-tuples of nodes $$$(u_1, u_2, u_3, u_4, u_5)$$$ that satisfy the following conditions. The answer should be computed modulo $$$998244353$$$.

• $$$u_2$$$ is an ancestor of $$$u_1$$$;
• $$$u_4$$$ is an ancestor of $$$u_5$$$;
• $$$u_3$$$ is the lowest common ancestor (LCA) of $$$u_2$$$ and $$$u_4$$$;
• The letters on nodes $$$u_1, u_2, u_3, u_4, u_5$$$ are 'a', 'b', 'c', 'd', 'e' respectively.

Long long ago, the universe existed as a high-dimensional space. Planets are neatly arranged here. Interstellar conflicts occur frequently, yet counterattacks are not allowed.

In an $$$n$$$-dimensional space, the coordinate of the $$$i$$$-th dimension is an integer within the range $$$[1, a_i]$$$. The set of all lattice points is defined as:

$$$$$$ \{(x_1, x_2, \dots, x_n) \mid 1 \le x_i \le a_i,\ x_i \in \mathbb{Z}\}. $$$$$$

Initially, all points satisfying $$$x_i \le b_i$$$ for every $$$i$$$ are colored black (every coordinate is no larger than the corresponding threshold $$$b_i$$$), and all other points are white.

Alice and Bob take turns to perform operations, and Alice moves first. In each turn, the current player must select a white point $$$P = (x_1, x_2, \dots, x_n)$$$. After the selection, all points $$$Q = (y_1, y_2, \dots, y_n)$$$ satisfying $$$y_i \ge x_i$$$ for every $$$i$$$ will be colored black. A player loses if they cannot choose any white point to operate on.

Both players adopt optimal strategies. For each test case, determine whether Alice has a winning strategy.

In a future autonomous interception drill, commander Alice uses $$$n$$$ unmanned interceptors (denoted as $$$A_1, A_2, \ldots, A_n$$$) to surround an intruding target $$$B$$$ controlled by Bob. All units move on a two-dimensional plane. Whether the interception succeeds depends not only on the initial layout, but also on the path planning strategies of both participants.

You are given the initial coordinates $$$A_i(x_i, y_i)$$$ of the $$$n$$$ interceptors and the starting position $$$(x_0, y_0)$$$ of target $$$B$$$ on the 2D plane.

Game Rules:

1. Equal speed movement: All interceptors $$$A_i$$$ and target $$$B$$$ move at a constant speed $$$v$$$ ($$$v \gt 0$$$) at all times. They can change direction instantly at any moment.
2. Interception rule: If at any moment $$$t \ge 0$$$, any interceptor $$$A_i$$$ coincides with target $$$B$$$ in position, the interception succeeds and Alice wins.
3. Optimal play: Alice controls all interceptors cooperatively to complete the interception, while Bob controls target $$$B$$$ to avoid being caught by any $$$A_i$$$ permanently. Both sides can track each other's positions in real time and will adopt optimal strategies.

There are $$$q$$$ independent queries. For each query, a new initial position $$$(x_0, y_0)$$$ of target $$$B$$$ is given. For every query, determine whether Alice is able to catch Bob under optimal play from both sides.

Then winter comes — the snow keeps falling and accumulating, eventually covering all sins. Finally spring arrives — along with the melting snow, all punishments are delivered.

Just cure whoever you can. There is no way to fix the problem setter who designed this problem.

As we all know, a person who is obsessed with bad endings just like this problem setter can never be cured. But if a problem can be solved with only slope optimization, it is still worth a try.

Given a sequence of $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$. You need to perform $$$q$$$ operations in total, choosing from the two types below. It is guaranteed that every number in the sequence always stays within the range $$$[1, 2 \times 10^5]$$$.

1. Add a positive integer $$$x$$$ to all elements in the interval $$$[l,r]$$$.

2. Consider a subarray $$$a_l, a_{l + 1}, \cdots ,a_r$$$ whose length is at least $$$2$$$. Split it into several consecutive segments, where each segment has a length of no less than $$$2$$$. Suppose a segment has length $$$L$$$ and elements $$$b_1, b_2, \cdots, b_L$$$. Let its variance be $$$$$$ \sigma^2=\frac{1}{L}\sum^L_{i=1}(b_i-\bar{b})^2 $$$$$$ Define the weight of this segment as $$$\sigma^2 L$$$. You need to find an optimal splitting scheme to minimize the total weight. Note that the defined weight is NOT equal to the variance.

"Why did it come to this? I finally met someone I love, and also gained a lifelong best friend. Two kinds of joy blend together, and this double joy brings endless more happiness. I was supposed to embrace a dreamlike happy life. But why... why has everything turned out like this?"

Given a positive integer $$$n$$$, consider all positive integers in the interval $$$[n, n^2]$$$.

A positive integer $$$k$$$ is defined as good if it meets both of the following requirements:

• $$$n \le k \le n^2$$$.
• For any positive integer $$$i$$$ in $$$[n, n^2]$$$ where $$$i \neq k$$$, we have $$$\gcd(i, k) = 1$$$.

For the given $$$n$$$, you are required to:

• Count how many good positive integers exist in $$$[n, n^2]$$$;
• Output any one of these good positive integers.

If only I had held the hero's hand instead of the commemorative coin back then...

There are $$$n$$$ commemorative coins arranged in a row. Initially, all coins are facing up.

In one operation, you can choose a consecutive segment of exactly $$$k$$$ coins and flip all of them.

Given a final state $$$s$$$ describing whether each coin is heads up or tails up, determine if it is possible to reach this state from the initial state using any number of operations (including zero operations).

wzj has invented a brand new Ludo game! This game comes with a huge board and a giant die.

wzj really enjoys this game, but he can never gather enough players to start a match. Other people think one full game takes far too much time, so no one wants to play with him.

He wants to prove that the game can end quickly if everyone plays with the optimal strategy. Unfortunately, he does not know how to calculate the exact number of turns.

Could you help him solve this problem?

The board has $$$n$$$ cells numbered from $$$1$$$ to $$$n$$$. Initially, wzj's piece is placed on cell $$$1$$$. There is an $$$m$$$-sided die. Each roll generates an integer chosen uniformly at random from $$$1$$$ to $$$m$$$.

In each turn, wzj first rolls the die. Let the result be $$$x$$$. After seeing $$$x$$$, he has two choices: move forward by $$$x$$$ steps, or skip the turn and stay in place.

• If he chooses to stay, the position of the piece remains unchanged.
• If he chooses to move $$$x$$$ steps. Suppose the current cell is $$$p$$$:
  • If $$$p + x \le n$$$, the piece moves to cell $$$p+x$$$.
  • If $$$p + x \gt n$$$, the piece will bounce back and land on cell $$$n - (p + x - n) = 2n - p - x$$$.

The goal is to reach cell $$$n$$$ as quickly as possible.

Under the optimal strategy (which minimizes the expected number of turns to reach cell $$$n$$$), calculate the expected number of turns needed for wzj to travel from cell $$$1$$$ to cell $$$n$$$.

You are participating in a programming contest. There are $$$n$$$ problems in total. The $$$i$$$-th problem has the following attributes:

1. $$$a_i$$$: you gain $$$a_i$$$ points for solving this problem;
2. $$$t_i$$$: it takes $$$t_i$$$ units of time to solve this problem;
3. $$$b_i$$$: you lose $$$b_i$$$ points for every unit of time that passes before you solve this problem.

Formally, if you solve the $$$i$$$-th problem at time $$$s$$$ (timed from the start of the contest), the actual score you get from this problem is $$$a_i - b_i \cdot s$$$.

The total duration of the contest is $$$T$$$. You can solve any number of problems in any order (you may choose not to solve some problems), but the total time consumed by all solved problems must not exceed $$$T$$$.

You need to maximize the total score you obtain.

The ACM team of BNU is recruiting new members!

After multiple rounds of selection, all candidates have successfully joined the team, except wzj and xyz, whose final spots are still pending.

You decide to team up with them for an ACM contest to evaluate their coding skills. The three of you share one computer during the contest. The problems are fairly easy, so you solve all of them effortlessly and assign a score to each problem. Then you let wzj and xyz take turns to write code for the problems. wzj moves first, and xyz moves second. Both of them hope to win your recognition, so they try to maximize their own total scores to show their ability.

There are $$$n$$$ problems in total, and each problem belongs to one of the following two types:

• Single-part problem: This problem has only one part, with a score of $$$h$$$.
• Two-part problem: It contains two subproblems (the first part and the second part), whose scores are $$$h_1$$$ and $$$h_2$$$ respectively. The second part can only be completed after the first part is finished. Note that these two parts can be completed by different players.

wzj and xyz take turns to make moves, with wzj moving first. On each turn, the current player must select and complete one problem from all currently available problems, and gain the score of that problem.

Definition of available problems:

• For a single-part problem: It is always available as long as it has not been completed.
• For the first part of a two-part problem: It is available if this part has not been completed.
• For the second part of a two-part problem: It becomes available only if the corresponding first part has been completed (by either player) and the second part itself remains unfinished.

The game ends after all problems are completed.

Both players aim to maximize their own total score. Given that both of them adopt optimal strategies, please calculate the final scores of wzj and xyz.

This in an interactive problem.

Note: This problem uses an adaptive interactor.

This problem was written on May 20th.

In this school contest, I committed three crimes.

The crime of adding $$$0$$$ to the data range, causing a division by zero error if the code does not handle it as a special case.

The crime of setting the upper bound of binary search to $$$10^{18} + 10^9$$$, and making intermediate variables reach the order of $$$10^{23}$$$, leading to an extremely error-prone upper bound and integer overflow in the code.

And... and there's more...

The felony of replacing the problem four days before the contest, creating a new problem, and intentionally writing a wrong interactor...

To test the support for interactors on the school contest platform, xyz tried to implement an adaptive interactor for the classic interactive template (binary number guessing). Unfortunately, he wrote the interactor incorrectly.

The description of the number guessing problem is as follows: The judge has a positive integer $$$x$$$ in the range $$$[1, 10^9]$$$. You need to guess the value of $$$x$$$ with no more than $$$100$$$ queries. For each query, you ask the judge for a positive integer $$$y$$$ in $$$[1, 10^9]$$$. The judge returns $$$1$$$ if $$$y \ge x$$$, and returns $$$0$$$ if $$$y \lt x$$$.

The logic of the wrong interactor designed by xyz is as follows: To maximize the number of subsequent queries required by the guessing program, the interactor should choose the response that results in a longer new interval. If the lengths are equal, either choice is acceptable (usually $$$0$$$ or $$$1$$$). In this way, after each response, the interval size is at least half of the original interval size (rounded up), making the number of queries approach the information-theoretic lower bound $$$\lceil \log_2 10^9 \rceil = 30$$$.

xyz believed that if the existing conditions only imply that $$$x$$$ lies in the interval $$$[l, r]$$$, the correct choice can be made by comparing $$$|y - l|$$$ and $$$|y - r|$$$. Thus, he implemented the following rules:

• If $$$|y - l| \gt |y - r|$$$, the interactor returns $$$1$$$;
• If $$$|y - l| \lt |y - r|$$$, the interactor returns $$$0$$$;
• If $$$|y - l| = |y - r|$$$, the interactor returns $$$0$$$ with a $$$50\%$$$ probability and $$$1$$$ with a $$$50\%$$$ probability.

The way to determine $$$l$$$ and $$$r$$$ in xyz's wrong interactor is as follows:

• If no query response is $$$1$$$ so far, then $$$r = 10^9$$$;
• Otherwise, let the values of queries with response $$$1$$$ be $$$a_1, a_2, \cdots, a_n$$$, then $$$r = \min_{i = 1}^n a_i$$$;
• If no query response is $$$0$$$ so far, then $$$l = 1$$$;
• Otherwise, let the values of queries with response $$$0$$$ be $$$b_1, b_2, \cdots, b_m$$$, then $$$l = \max_{i = 1}^m b_i + 1$$$.

According to the definition of the response, the true value $$$x$$$ must lie within the interval $$$[l, r]$$$, and this is the minimal possible interval derived from the existing responses.

For example, if it is currently only known that $$$x$$$ is in the interval $$$[5, 9]$$$ (i.e., $$$l=5, r=9$$$), when querying $$$y = 7$$$, xyz's wrong interactor compares $$$|7-5|=2$$$ and $$$|7-9|=2$$$. Since they are equal, it returns $$$1$$$ with a $$$50\%$$$ probability and $$$0$$$ with a $$$50\%$$$ probability. If it returns $$$1$$$, the new interval becomes $$$[5, 7]$$$; if it returns $$$0$$$, the new interval becomes $$$[8, 9]$$$. This wrong interactor has a $$$50\%$$$ chance to choose the longer interval, which affects subsequent interval updates.

Note: Since xyz's interactor is implemented incorrectly, $$$l \le r$$$ is NOT guaranteed during the interaction. The response is only determined by the relative values of $$$|y - l|$$$ and $$$|y - r|$$$.

Now, there are two types of interactors. The first is the correct interactor, which gives logically consistent results in all cases (it is an adaptive interactor, but its adaptation method may differ from any of those described in the problem statement). The second is xyz's wrong interactor, which interacts following the rules above. You can make no more than $$$100$$$ queries to the interactor to determine which type you are interacting with.

Note: The correct implementation of the adaptive interactor required to solve this problem is as follows:

• If $$$|y - l + 1| \gt |y - r|$$$, the interactor returns $$$1$$$;
• If $$$|y - l + 1| \lt |y - r|$$$, the interactor returns $$$0$$$;
• If $$$|y - l + 1| = |y - r|$$$, the interactor returns $$$0$$$ with a $$$50\%$$$ probability and $$$1$$$ with a $$$50\%$$$ probability.

Note: The interactor in this problem will not adapt its type. For each test case, the type of interactor is pre-determined before any queries are made.

This problem contains multiple test cases. The first line contains a positive integer $$$T$$$ $$$(1 \le T \le 100)$$$, denoting the number of test cases.

For each test case, repeat the following steps:

1. You may output a query in the format ? $$$y$$$, where $$$y$$$ is an integer satisfying $$$1\le y\le 10^9$$$. The interactor will return an integer $$$0$$$ or $$$1$$$ on a separate line. See the problem statement for the exact meaning of the response.
2. When you can determine the conclusion, output ! correct or ! wrong, indicating that you think the interactor is of the correct type or the wrong type, respectively. After this output, if there are subsequent test cases, the process will automatically move to the next one; if it is the last test case, the program should exit normally.

• The number of queries per test case must not exceed $$$100$$$. If exceeded, the interactor will return Wrong Answer and terminate the program immediately.
• You must output exactly one conclusion (! correct or ! wrong) for each test case, otherwise it will be judged as incorrect.

You must flush the standard output buffer after every output operation, otherwise the interactor may not receive your output in time, resulting in a time limit exceeded or wrong answer.

Methods to flush the output in common programming languages are as follows:

• C++: std::cout.flush();
• C: fflush(stdout);
• Python: sys.stdout.flush() (requires import sys)
• Other languages: Please refer to the corresponding documentation for methods to flush the standard output.

You have an initial string $$$S$$$, and $$$q$$$ operations will be performed sequentially. There are three types of operations:

1. Add Character: Append a given character $$$c$$$ to the end of the string.
2. Delete from End: Delete $$$k$$$ characters from the end of the string. If $$$k$$$ is greater than the current length of the string, clear the entire string.
3. Copy and Concatenate: Make a copy of the current string and append it to the original string (i.e., new string = original string + original string).

After all operations are completed, you need to answer: what is the $$$P$$$-th character of the final string? The indices start from $$$1$$$. It is guaranteed that $$$P$$$ does not exceed the length of the final string.

Given a sequence of prime numbers $$$p_1, p_2, \dots, p_n$$$, where each $$$p_i$$$ is a prime number no greater than $$$10^7$$$.

Find two intervals $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ that satisfy $$$1 \le l_1 \le r_1 \le n$$$, $$$1 \le l_2 \le r_2 \le n$$$ and $$$(l_1, r_1) \neq (l_2, r_2)$$$, such that the product of all elements inside the two intervals is equal:

$$$$$$ \prod_{i=l_1}^{r_1} p_i = \prod_{j=l_2}^{r_2} p_j $$$$$$

You may output any valid pair if multiple solutions exist. If no such pair of distinct intervals exists, output -1.