You are given a program consisting of $$$n$$$ instructions executed by a processor with a single integer register $$$A$$$, initially equal to $$$0$$$. Each instruction is one of two types:

• "+ v" — performs $$$A := A + v$$$;
• "= v" — performs $$$A := v$$$.

The instructions in the program are numbered from $$$1$$$ to $$$n$$$. Each instruction $$$i$$$ initially has timestamp $$$i$$$.

Some instructions are marked as asynchronous. If instruction $$$i$$$ is asynchronous, its timestamp can be changed to any real number greater than $$$i$$$.

After all timestamp adjustments, all timestamps must be distinct. The processor then executes the instructions in order of increasing timestamp.

Determine the number of distinct final values of $$$A$$$ that can be obtained after all instructions have been executed, considering all possible choices of asynchronous instruction timestamps.

ICPC is considering sending out contest souvenirs via a delivery service. The delivery service provides multiple types of packing boxes, each shaped as a rectangular parallelepiped.

Unfortunately, there is no way to know which packing box type will be available on the shipping day, so ICPC needs to choose a souvenir box size that fits inside every packing box.

According to the shipment rules, the souvenir box must also be a rectangular parallelepiped. When placed inside a packing box, the souvenir box may be rotated, but its sides must remain parallel to the sides of the packing box. Extra space is not an issue, as it will be filled with plastic wrap.

Help ICPC determine the maximum possible volume of a souvenir box that fits inside all of the packing boxes.

Binary formats often use compact representations for integers. Consider writing a 32-bit unsigned integer to a file: you must always reserve 4 bytes to represent it (remember, 8 bits make one byte). However, in many real-life applications, integer values tend to be small. Writing these small values using a fixed 4-byte representation results in files that are mostly filled with zero bytes.

To make the representation more compact, we introduce the following encoding scheme. Each value is represented as a sequence of bytes $$$b_1, b_2, \ldots, b_k$$$, where each $$$b_i$$$ is an integer between $$$0$$$ and $$$255$$$, inclusive. The most significant bit of each byte serves as a continuation flag, and the lower $$$7$$$ bits carry the actual data. If the continuation flag is $$$1$$$, more bytes follow; for the last byte, it is $$$0$$$. The representation is big-endian, meaning that $$$b_1$$$ contains the most significant bits of the encoded value.

For example, here's how to find the compact representation of $$$n = 112025$$$. First, we find its binary representation:

Next, we split it into 7-bit chunks, padding with zeros on the left if necessary:

The first two chunks have a following chunk, so the corresponding bytes have their most significant bit set to $$$1$$$. The last chunk has no following chunk, so its most significant bit is $$$0$$$. This gives us:

You are given an integer $$$n$$$, and your task is to find its compact representation.

The NWRRC security server has a final access check for teams that try to submit their solutions to the secret hidden problem.

To pass the check, the team must enter three passwords $$$s$$$, $$$t$$$, and $$$u$$$ that the system will accept. Each password must be a non-empty string consisting of at most $$$5000$$$ lowercase English letters.

The rules of the server are public:

• The distance between $$$s$$$ and $$$t$$$ should be equal to $$$a$$$.
• The distance between $$$s$$$ and $$$u$$$ should be equal to $$$b$$$.
• The distance between $$$t$$$ and $$$u$$$ should be equal to $$$c$$$.

The distance between two strings $$$s_1$$$ and $$$s_2$$$ is the minimum number of single-character operations (insert one character, remove one character, or replace one character) needed to convert string $$$s_1$$$ into string $$$s_2$$$. This metric is also known as the Levenshtein distance.

The server gives access to the hidden problem if and only if all described conditions are satisfied. Your goal is to construct a triple of passwords to unlock the hidden problem or determine that it is impossible.

This is an interactive problem.

An infinite square grid is hidden from you. Every cell is identified by a pair of integers $$$(x, y)$$$ and is randomly colored either black or white with $$$50\%$$$ probability for each color, independently of other cells.

Two cells are considered adjacent if they share an edge or a corner. Thus, every cell $$$(x, y)$$$ has $$$8$$$ adjacent cells: $$$(x-1, y-1)$$$, $$$(x-1, y)$$$, $$$(x-1, y+1)$$$, $$$(x, y-1)$$$, $$$(x, y+1)$$$, $$$(x+1, y-1)$$$, $$$(x+1, y)$$$, and $$$(x+1, y+1)$$$.

A set of cells $$$S$$$ is called 8-connected if for any two cells in $$$S$$$, there exists a path between them using only cells from $$$S$$$, where consecutive cells in the path are adjacent.

In one query, you can learn the color of any cell on the grid. Your task is to find an 8-connected set of $$$n$$$ cells such that all cells in the set have the same color.

You need to solve $$$t$$$ test cases. In each test case, the grid is colored randomly and independently of the other test cases.

You are allowed to make at most $$$30\,000$$$ queries in total over all test cases.

In each test case, you can make zero or more queries to learn the colors of grid cells.

To make a query, print a line:

• ? $$$x$$$ $$$y$$$

Once you are ready to present an 8-connected set of $$$n$$$ cells of the same color, print a line:

• ! $$$c$$$ $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ $$$\ldots$$$ $$$x_n$$$ $$$y_n$$$

where $$$c$$$ is a letter denoting the color of the cells in the set ('B' for black and 'W' for white), and $$$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$$ are the $$$n$$$ distinct cells in the set ($$$-10^9 \le x_i, y_i \le 10^9$$$). The interactor does not print anything in response to this line.

After printing the set, proceed to the next test case, or terminate the program if this was the last one.

You are allowed to make at most $$$30\,000$$$ queries in total over all test cases (not including the lines that print the sets). If you exceed this limit, the interactor will print $$$0$$$ instead of its usual response, and your program should terminate immediately to guarantee the "Wrong Answer" verdict.

The interactor is not adaptive: all random grids used in the tests have been pre-generated and remain the same across all submissions.

Felix is studying basic arithmetic at school. Today he learned division. As a final task, he calculated the result of the division of a positive integer $$$a$$$ by a positive integer $$$b$$$. The result was a positive integer $$$c$$$, since $$$a$$$ was divisible by $$$b$$$. Felix wrote $$$a \div b = c$$$ in his notebook and went outside to play football.

His little sister Fiona had been watching his studies with great interest. When Felix left, she decided to play a little trick on him: she took his notebook and erased the '$$$\div$$$' sign from the equation. As a result, the left-hand side of the equation became a single string of digits $$$s$$$.

Once Felix came back, he saw $$$s = c$$$ in his notebook. Unfortunately, he forgot the original values of $$$a$$$ and $$$b$$$. Now he needs to split $$$s$$$ back into two parts using the '$$$\div$$$' sign to restore a correct division equation.

Help Felix find positive integers $$$a$$$ and $$$b$$$ such that $$$s$$$ is the concatenation of the decimal representations of $$$a$$$ and $$$b$$$, and $$$a \div b = c$$$.

There are $$$n$$$ friends and $$$n$$$ houses in Chess City, both numbered from $$$1$$$ to $$$n$$$, where friend $$$i$$$ lives in house $$$i$$$. The houses are connected by $$$m$$$ bidirectional roads, forming a connected network.

Chess City also has $$$n$$$ virtual chess clubs, numbered from $$$1$$$ to $$$n$$$. Each friend must choose exactly one club to join. These choices do not need to be distinct, so some clubs might not have any members.

When friend $$$i$$$ hosts a chess party, it is attended by every friend who belongs to the same club as friend $$$i$$$ and lives in a house directly connected to house $$$i$$$ by a road. The party is considered successful if the total number of attendees, including friend $$$i$$$, is even; in this case, they can all play chess simultaneously.

Choose a club for each friend so that every friend's party is successful, or report that it is impossible.

Hermione loves to play the following computer game, in which the player controls an unordered multiset of integers. Initially, the multiset is empty and the player's score is $$$0$$$. At any moment in the game, the multiset contains at most $$$k$$$ integers (not necessarily distinct). In one turn, the player can choose one of the following moves:

• Insert. Choose an integer $$$2$$$ or $$$4$$$ and insert it into the multiset. This move does not change the score, and it is only allowed if the size of the multiset before the move is strictly less than $$$k$$$.
• Merge. Choose an integer $$$x$$$ such that the multiset contains at least two copies of $$$x$$$. Remove two copies of $$$x$$$ from the multiset, and insert one copy of $$$2x$$$ into the multiset. This move adds the value $$$2x$$$ to the player's score.

The player can stop the game after any turn, at which point the player's score becomes final.

Hermione has been on vacation for the whole summer, and she hasn't played the game in a while. Today, she opened the game on her laptop and saw the leaderboard with the highest scores she's ever had: $$$h_1, h_2, \ldots, h_n$$$ in some order. Now she is curious how she managed to achieve those scores.

For each $$$h_i$$$, find any multiset of integers that Hermione could have at the end of the game if her final score was $$$h_i$$$, or determine that it is impossible to achieve such a score.

Isaac is a biologist who specializes in diagnosing viral diseases. The virus modifies the host genome (a sequence of genes) by altering it to suit its own needs. Isaac is writing a paper investigating viral infection in genomes. He has some samples and asks you to help analyze them.

For simplicity, we will assume that the viral genome consists of genes $$$1, 2, \ldots, n$$$ in this order. The host genome is a permutation of genes $$$1, 2, \ldots n$$$: it consists of genes $$$a_1, a_2, \ldots, a_n$$$ in this order.

Consider a genomic segment $$$[l; r]$$$ consisting of genes $$$a_l, a_{l+1}, \ldots, a_r$$$. The infection level of this segment is measured as the length of the longest subsequence of genes shared with the viral genome. Formally, the infection level is the maximum $$$k$$$ such that there exist $$$l \le i_1 \lt i_2 \lt \dots \lt i_k \le r$$$ for which the inequalities $$$a_{i_1} \lt a_{i_2} \lt \dots \lt a_{i_{k}}$$$ hold.

To analyze the genome, Isaac needs to estimate the infection levels of $$$q$$$ genomic segments. To secure the funding, Isaac only needs approximate results: an error factor of up to $$$1.5$$$ is allowed.

The judges of NWRRC came up with $$$n$$$ problems on a similar topic and decided to use them for $$$n$$$ consecutive years, one problem per year. The only question was: in what order should they be used?

Each problem's name consists of two words. Let's call two names similar if either their first words are the same or their second words are the same. For example, eight shaped and eight connected are similar, while hello world and world hello are not.

The judges decided to implement the following rule: in the first year, they chose a problem arbitrarily. In every subsequent year, if there was a problem with a name similar to the previous year's problem that was still unused, they chose one of such problems; otherwise, they chose any unused problem.

You are given the names of the problems in chronological order of their use. Determine whether the judges correctly followed the rule above, or if they made a mistake.

Katniss is in a very long straight tunnel and wants to get out of it. She can move along the tunnel in both directions. There is exactly one hatch in the tunnel, and if she reaches it, she can exit.

Unfortunately, it's not that simple. There are grates blocking the entire width of the tunnel at $$$n$$$ locations. The grates are locked, and Katniss cannot pass through a grate until she unlocks it. Fortunately, there are $$$n$$$ keys located at $$$n$$$ points along the tunnel. Each grate can be unlocked by exactly one of these $$$n$$$ keys. Once a grate is unlocked, Katniss can freely and repeatedly pass through it. She can pick up and hold an unlimited number of keys.

Katniss knows her own location, as well as the locations of all $$$n$$$ keys, all $$$n$$$ grates, and the hatch. She also knows which key unlocks which grate. Determine the minimum distance she must travel to escape.

Lucy is a frequent arcade visitor. All machines at the arcade give out tickets to exchange for prizes! Lucy's favorite machine works as follows.

The machine only has two buttons: "Roll" and "Withdraw". Whenever Lucy presses "Roll", the machine increases the counter on the screen by a randomly generated real number between $$$0$$$ and $$$d$$$. At any moment, she can press "Withdraw" to get the number of tickets equal to the counter, which gets reset. In case it's not an integer, the machine generously rounds the counter up before handing out the tickets.

More formally, the machine stores a real number $$$S$$$, initially equal to 0. On each "Roll" press, the machine generates $$$\Delta$$$ — a random real number picked uniformly from the interval $$$(0, d)$$$. Then, $$$S$$$ increases by the value of $$$\Delta$$$. When the "Withdraw" button is pressed, the machine rounds $$$S$$$ up, giving the player $$$\lceil S \rceil$$$ tickets, and then resets $$$S$$$ back to zero. Lucy can see the value of $$$S$$$ on the screen at any moment with as much precision as she wants, and she can use it to decide whether to roll or withdraw.

Lucy has enough arcade tokens to press "Roll" $$$n$$$ times, and "Withdraw" $$$k$$$ times. Find a strategy that maximizes the expected number of tickets Lucy can get, and print this maximum expected number.