Hyrule is entering the flu season.

Hyrule consists of $$$n$$$ cities, which are connected by $$$m$$$ directed roads. The capital (city numbered $$$1$$$) can be reached from all cities through these roads.

The flu season will last for $$$q$$$ days. On the $$$i$$$-th day at noon, the flu virus will start spreading from city $$$a_i$$$. The virus will spread along the roads to other cities. The virus spreads very quickly, so it can be assumed that all cities reachable from $$$a_i$$$ will be infected immediately. As the capital city of Hyrule, city $$$1$$$ is crucial for the whole country. If the virus that starts spreading on the $$$i$$$-th day reaches the capital, there will be an economic loss cost of $$$b_i$$$.

To prevent the virus from spreading, Auru can deploy a virus filter in a city each night (including the night before the first day). Deploying a virus filter in city $$$i$$$ has a deployment cost of $$$c_i$$$. The virus cannot spread through the city equipped with a virus filter, and that city will also remain uninfected. If the virus were to start spreading from a city equipped with a virus filter, the virus would simply disappear without infecting any cities. The deployed virus filter remains effective until Auru deploys a new filter in another city. (In other words, there can be at most one virus filter at a time.)

Auru wants to know: for each $$$i = 1, 2, \dots, q$$$, considering only the viruses in the first $$$i$$$ days, what is the minimum value of "economic loss cost + deployment cost".

Betty has a bracket sequence $$$s$$$ of length $$$n$$$, which consists of eight types of brackets: "()[]{}<>". Additionally, she has $$$m$$$ sub-bracket sequences, and the $$$i$$$-th sub-bracket sequence $$$t_i$$$ is the sequence formed by concatenating the characters from the $$$l_i$$$-th to the $$$r_i$$$-th position of $$$s$$$, i.e., $$$t_i = s_{l_i}s_{l_i+1} \cdots s_{r_i}$$$.

Betty wants to know, by taking out several pairs from these $$$m$$$ sub-bracket sequences and concatenating sequences in the same pair, how many valid bracket sequences$$$^\dagger$$$ can be formed at most? Formally, you need to find as many pairs $$$(a_i, b_i)$$$ as possible such that:

1. For any integer $$$x$$$ from $$$1$$$ to $$$m$$$, the sum of its occurrences in $$$a$$$ and its occurrences in $$$b$$$ should be no larger than $$$1$$$.
2. For any pair $$$(a_i, b_i)$$$, $$$t_{a_i}t_{b_i}$$$ is a valid bracket sequence$$$^\dagger$$$.

$$$^\dagger$$$ A bracket sequence $$$x$$$ is valid if and only if it satisfies one of the following conditions:

• $$$|x| = 0$$$, i.e., $$$x$$$ is an empty string.
• $$$x = LyR$$$, where $$$y$$$ is a valid bracket sequence, and $$$L$$$, $$$R$$$ are left and right brackets of the same type (i.e., $$$L=$$$ "(" and $$$R=$$$ ")", or $$$L=$$$ "[" and $$$R=$$$ "]", or $$$L=$$$ "{" and $$$R=$$$ "}", or $$$L=$$$ "<" and $$$R=$$$ ">").
• $$$x = y_1y_2$$$, where both $$$y_1$$$ and $$$y_2$$$ are valid bracket sequences.

The pirates have just seized a giant gold coin!

To determine the ownership of this gold coin, they decided to select the owner using the following method:

Let the current number of remaining pirates be $$$n$$$. The pirates line up in a queue, and the pirates at positions $$$1, 1+k, 1+2k, \dots, 1+(\lceil\frac{n}{k}\rceil - 1) k$$$ are eliminated. This operation is repeated until only one pirate remains. The final remaining pirate will receive the gold coin.

Charlie is the smartest among the pirates. He wants to know where he should stand initially to be the last pirate remaining and win the coin.

David has just obtained $$$n$$$ Russian nesting dolls of distinct sizes. He arranges these dolls in a row from left to right, where the $$$i$$$-th position contains a doll of size $$$a_i$$$.

Let the size of the smallest doll in the $$$i$$$-th position be $$$l_i$$$, and the size of the largest one be $$$r_i$$$. Dolls over two adjacent positions $$$i$$$ and $$$i+1$$$ can be merged if and only if $$$r_i \lt l_{i+1}$$$ or $$$r_{i+1} \lt l_i$$$. The new nesting doll will contain all the dolls from the original $$$i$$$-th and $$$i+1$$$-th positions and will be placed in the $$$i$$$-th position. All dolls in positions greater than $$$i+1$$$ will shift left by one position to fill the gap.

For example, when $$$n=4, a=[2,1,4,3]$$$, David can:

1. Merge the dolls in positions $$$1$$$ and $$$2$$$. Now the remaining dolls have sizes $$$[(1,2), (4), (3)]$$$.
2. Merge the dolls in positions $$$2$$$ and $$$3$$$. Now the remaining dolls have sizes $$$[(1,2), (3,4)]$$$.
3. Merge the dolls in positions $$$1$$$ and $$$2$$$. Now all the dolls have been merged into one position.

How many merge operations at most can David perform under an optimal strategy?

This is an interactive problem.

Emily has a tree containing $$$n$$$ nodes, where the weight of the node numbered $$$i$$$ is $$$w_i$$$. Node $$$1$$$ is the root node, and the weight of the root node is $$$0$$$.

Emily wants you to guess the weight of each node. Specifically, you can make at most $$$n$$$ queries, with the $$$i$$$-th query containing two integers $$$u_i$$$ and $$$v_i$$$. If the simple path from $$$u_i$$$ to $$$v_i$$$ contains exactly $$$k$$$ edges, Emily will tell you the bitwise XOR$$$^{\dagger}$$$ of the weights of all the nodes on the simple path from node $$$u_i$$$ to node $$$v_i$$$ (including the endpoints). Otherwise, Emily will respond with "-1", indicating that she does not want to answer that question. Emily is very busy, so she will not start answering until you have asked all your questions.

Of course, you may not be able to guess the weights of all nodes with no more than $$$n$$$ queries for some cases. In such cases, you should not make any queries and instead directly tell Emily that it is impossible.

$$$^{\dagger}$$$The bitwise XOR operation refers to the addition of each bit of two binary numbers under modulo $$$2$$$. For example: $$$(0011)_2$$$ $$$\oplus$$$ $$$(0101)_2$$$ $$$=$$$ $$$(0110)_2$$$.

First, you need to determine whether it is possible to guess the weights of all nodes within $$$n$$$ queries. If not, your program should output "No" and exit immediately. Otherwise, your program should output "Yes" and proceed to querying. You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

To make a query, output all your $$$q$$$ queries at once in the format "? $$$q$$$ $$$u_1$$$ $$$v_1$$$ $$$u_2$$$ $$$v_2$$$ $$$\dots$$$ $$$u_q$$$ $$$v_q$$$" ($$$1 \leq q \leq n$$$, $$$1 \leq u_i, v_i \leq n$$$). After flushing your output, your program should read a line containing $$$q$$$ integers. The $$$i$$$-th integer represents the response to the $$$i$$$-th query.

To guess the weights, output your guess in the format "! $$$w_2$$$ $$$w_3$$$ $$$\dots$$$ $$$w_n$$$" ($$$0 \leq w_i \lt 2^{30}$$$). After flushing your output, your program should exit immediately.

Note that the answer for each test case is pre-determined. That is, the interactor is not adaptive. Also, note that your guess does not count as a query.

To flush your output, you can use:

• fflush(stdout) (if you use printf) or cout.flush() (if you use cout) in C and C++.
• System.out.flush() in Java and Kotlin.
• stdout.flush() in Python.

Frank is fascinated by the beauty of numbers.

One day, Frank was watering flowers in his garden. Looking at the beautiful petals, he thought it would be wonderful if each flower could grow numbers.

So, he took out paper and pen and started sketching his ideal "number flower". An undirected connected graph is called a "number flower" if and only if it satisfies the following three conditions:

1. If the graph contains $$$n$$$ nodes, these nodes should be labeled from $$$1$$$ to $$$n$$$.
2. The graph contains exactly $$$n-1$$$ edges. No node has a degree greater than $$$2$$$ except for node $$$1$$$.
3. Nodes directly connected to node $$$1$$$ are called key nodes. All key nodes have pairwise coprime labels. For each non-key node (except node $$$1$$$), its label is a multiple of the nearest key node's label, and the labels along the simple path from the non-key node to its nearest key node are monotonically decreasing.

Given an integer $$$n$$$, how many different "number flowers" with $$$n$$$ nodes are there? Two graphs $$$G_1$$$ and $$$G_2$$$ are considered the same if and only if for any edge $$$(u, v)$$$ in $$$G_1$$$, a corresponding edge $$$(u, v)$$$ exists in $$$G_2$$$.

Since the answer is huge, you only need to output it modulo a prime number $$$p$$$.

Given two integers $$$a$$$ and $$$b$$$, you can perform one of the following two operations in each round:

• If $$$a \gt 0$$$, then reduce the value of $$$a$$$ by $$$\gcd(a, b)$$$ .
• If $$$b \gt 0$$$, then reduce the value of $$$b$$$ by $$$\gcd(a, b)$$$ .

Grace wants to know the minimum number of rounds needed to make both $$$a$$$ and $$$b$$$ become $$$0$$$.

$$$^{\dagger}$$$ $$$\gcd(x, y)$$$ denotes the greatest common divisor of $$$x$$$ and $$$y$$$. For example, $$$\gcd(6, 8) = 2, \gcd(7, 5) = 1$$$. The values of $$$\gcd(x, 0)$$$ and $$$\gcd(0, x)$$$ are defined as $$$x$$$.

Hana recently needs to develop a radar system to monitor abnormal activities across the archipelago she manages.

There are $$$n$$$ islands in the ocean, and the $$$i$$$-th island is located at coordinates $$$(x_i, y_i)$$$, which can be treated as a point on the plane. Assume the radar has a scanning angle range of $$$\alpha$$$. When the radar is rotated to an angle $$$\theta$$$, it can monitor all the islands located within the angular range $$$[\theta - \frac{\alpha}{2}, \theta + \frac{\alpha}{2}]$$$.

Hana is currently low on funds, so she wants to minimize the cost of building the radar. She wants to know, when the radar is placed at the origin $$$(0,0)$$$, what the minimum scanning angle $$$\alpha$$$ should be to ensure that for any angle $$$\theta$$$, the radar can monitor at least $$$k$$$ islands.

Ivan has $$$n$$$ types of items, with an infinite supply of each type. The weight of the $$$i$$$-th type of item is $$$w_i$$$.

Ivan wants to know whether it is possible to select exactly $$$n$$$ items such that the total weight of the selected items equals $$$m$$$.

Jessica is a master of sorting algorithms, proficient in selection sort, insertion sort, bubble sort, and many others. Therefore, she decided to host a sorting competition.

The competition takes place on a permutation$$$^{\dagger}$$$ $$$p$$$ of length $$$n$$$, with two participants: Alice and Bob. The two players take turns performing operations, with the first player being decided by a coin toss. If the sequence is in ascending order after any player's turn, Alice wins immediately. If Alice cannot win within a finite number of turns, Bob is considered the winner.

On Alice's turn, she can choose any two positions $$$i,j$$$ ($$$i \neq j, 1 \leq i,j \leq n$$$) in the permutation and swap $$$p_i$$$ and $$$p_j$$$. On Bob's turn, he can select two adjacent positions $$$i,i+1$$$ ($$$1 \leq i \lt n$$$) and swap $$$p_i$$$ and $$$p_{i+1}$$$. Neither player is allowed to skip their turn.

Given the permutation $$$p$$$ and the name of the player who operates first, determine who will win the game if both players play optimally.

$$$^{\dagger}$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is a $$$4$$$ in the array).

This is an interactive problem.

Kevin is dissatisfied with his MBTI, so he asked Doraemon for a magical machine: the MBTI converter.

The MBTI converter can convert the MBTI attributes of $$$8$$$ people at a time. It will generate a "random" new MBTI for all individuals based on their initial MBTIs and a $$$32$$$-bit key $$$k$$$.

Kevin carefully studied this machine and found that the "random" MBTI it generates actually follows a certain pattern. The machine mainly includes three basic structures that shuffle the MBTI: "xor", "perm", and "mix". Each of these structures takes the MBTIs of $$$8$$$ individuals as input and outputs $$$8$$$ MBTIs as a result. In each structure, the input $$$8$$$ MBTIs are denoted as $$$in_0, in_1, in_2, \cdots, in_7$$$ and the output $$$8$$$ MBTIs are denoted as $$$out_0, out_1, out_2, \cdots, out_7$$$. For convenience, Kevin replaces each MBTI with a hexadecimal number according to the following table.

"xor" Structure:

The xor structure flips certain attributes of the MBTI based on the key $$$k$$$.

Let $$$k_j$$$ be the $$$j$$$-th binary bit of the key $$$k$$$ ($$$0 \leq j \lt 32$$$). The functionality of the xor structure can be expressed as: $$$$$$ out_i = in_i \oplus (\overline{k_{4i+3}k_{4i+2}k_{4i+1}k_{4i}})_2 $$$$$$ where $$$\oplus$$$ denotes the bitwise XOR$$$^{1}$$$.

"perm" Structure:

The perm structure replaces the MBTI, where each MBTI is replaced by another fixed MBTI.

The functionality of the perm structure can be expressed as: $$$$$$ out_i = p_{in_i} $$$$$$ where $$$p$$$ is a fixed array of length $$$16$$$ with the following values:

"mix" Structure:

The mix structure is used to mix the MBTIs of different people, with each output determined by two inputs.

The mix structure requires an intermediate array $$$t$$$ of length $$$8$$$, defined as: $$$$$$ t_i = \begin{cases} in_i \ll 1 & 0 \leq in_i \lt 8 \\ ((in_i \oplus 8) \ll 1) \oplus 3 & 8 \leq in_i \lt 16 \\ \end{cases} $$$$$$ where $$$\oplus$$$ denotes the bitwise XOR$$$^{1}$$$ and $$$\ll$$$ denotes logical left shift of four binary digits$$$^{2}$$$.

The functionality of the mix structure can be expressed as: $$$$$$ out_i = in_{i \ggg 1} \oplus (t_{(i \ggg 1) \oplus 1}) $$$$$$ where $$$\oplus$$$ denotes the bitwise XOR$$$^{1}$$$, and $$$\ggg$$$ denotes circular right shift of three binary digits$$$^{3}$$$.

The initial $$$8$$$ MBTIs will sequentially go through $$$19$$$ structures to produce the final output of $$$8$$$ MBTIs. These structures are: xor, perm, mix, xor, perm, mix, xor, perm, mix, xor, perm, mix, xor, perm, mix, xor, perm, mix, xor, which is six consecutive rounds of "xor, perm, mix" followed by an "xor".

Users of this machine typically hope to obtain a specific MBTI. Unfortunately, when Doraemon built this machine, he encapsulated the key $$$k$$$ inside the machine and refused to tell Kevin the value of the key. Thus, Kevin turned to you, the clever one. Kevin hopes you can construct some inputs (not exceeding $$$4096$$$, or the machine may be damaged), test run to obtain the corresponding outputs, and then analyze the value of the key. This way, he can write a program to predict the output for each input, allowing everyone to get their desired MBTI.

Can you accomplish this task?

$$$^{1}$$$ Bitwise XOR refers to performing the modulo $$$2$$$ addition operation on each corresponding bit of two binary numbers. For example: $$$(0011)_2$$$ $$$\oplus$$$ $$$(0101)_2$$$ $$$=$$$ $$$(0110)_2$$$.

$$$^{2}$$$ $$$x \ll y$$$ means to logically left shift the binary number $$$x$$$ by $$$y$$$ bits, discarding the overflow and filling the vacated parts with 0. For example: $$$(1100)_2$$$ $$$\ll$$$ $$$1$$$ $$$=$$$ $$$(1000)_2$$$, $$$(1001)_2$$$ $$$\ll$$$ $$$1$$$ $$$=$$$ $$$(0010)_2$$$.

$$$^{3}$$$ $$$x \ggg y$$$ means to circularly right shift the binary number $$$x$$$ by $$$y$$$ bits. For example: $$$(101)_2$$$ $$$\ggg$$$ $$$1$$$ $$$=$$$ $$$(110)_2$$$, $$$(110)_2$$$ $$$\ggg$$$ $$$1$$$ $$$=$$$ $$$(011)_2$$$.

To run the MBTI converter, please output "? $$$in_7in_6in_5in_4in_3in_2in_1in_0$$$" ($$$in_i \in \{0-9,a-f\}$$$), where $$$in_i$$$ is the hexadecimal value corresponding to the $$$i$$$-th input MBTI. You may perform this operation at most $$$4096$$$ times. After flushing your output, please read the output of the MBTI converter in the format "$$$out_7out_6out_5out_4out_3out_2out_1out_0$$$" ($$$out_i \in \{0-9,a-f\}$$$).

To answer for the value of $$$k$$$, please output "! $$$k$$$" ($$$0 \leq k \lt 2^{32}$$$), where $$$k$$$ is the decimal representation of the value you believe the key $$$k$$$ to be. You may perform this operation at most once. After performing the operation, you should exit your program immediately.

If you run the MBTI converter more than $$$4096$$$ times, or if your output contains invalid characters, the interactor will output "-1". Upon receiving such a response, you should immediately exit your program, and you will receive a "Wrong Answer" result. Otherwise, the result is uncertain, as you will attempt to read data from a closed output stream.

To flush your output, you can use:

• fflush(stdout) (if you use printf) or cout.flush() (if you use cout) in C and C++.
• System.out.flush() in Java and Kotlin.
• stdout.flush() in Python.

Fried-chicken is a devoted player of Hearthstone. Since the game resumed operations in the Chinese mainland, he has been obsessed with it and reached Silver 2 rank in Standard mode. Today, while ranking up using Death Knight, he encountered a formidable opponent, Stewed-chicken, and was left with just $$$1$$$ Health. To survive, Fried-chicken must eliminate all of Stewed-chicken's minions. Fortunately, he can use spell cards and his minions' attacks to achieve this goal.

Specifically, this game involves two factions: Fried-chicken and Stewed-chicken. Each faction has some minions. The $$$i$$$-th minion has $$$h_i$$$ Health. It is now Fried-chicken's turn, and each of his minions can attack any one minion from the opposing faction at most once. When one minion attacks another, both minions lose $$$1$$$ Health. If a minion's Health is reduced to $$$0$$$ or less, it dies and can no longer attack or be attacked.

To achieve his goal, Fried-chicken casts the spell "Threads of Despair," causing every minion to explode upon death, which reduces the Health of all minions by $$$1$$$. If the explosion causes the death of other minions, other minions will also explode immediately. Fried-chicken cannot have his minions attack other minions until all explosion effects have finished. After casting the spell, Fried-chicken can make his minions attack Stewed-chicken's minions in any order he chooses. He wants to know if there exists an attack order that allows Fried-chicken to eliminate all of Stewed-chicken's minions.

Mary loves constructing matrices!

Today, Mary wants to fill a permutation$$$^{\dagger}$$$ of length $$$n \times m$$$ into an $$$n \times m$$$ matrix $$$A$$$, such that the sum of any two adjacent elements is unique.

In other words, for any $$$1 \leq x_1,x_2,x_3,x_4 \leq n, 1 \leq y_1,y_2,y_3,y_4 \leq m$$$, if all of the following conditions are satisfied:

• $$$x_2 \geq x_1, y_2 \geq y_1, x_4 \geq x_3, y_4 \geq y_3$$$;
• $$$|x_2-x_1|+|y_2-y_1|=1, |x_4-x_3|+|y_4-y_3|=1$$$;
• $$$(x_1,y_1) \neq (x_3,y_3)$$$ or $$$(x_2,y_2) \neq (x_4,y_4)$$$;

For example, when $$$n=2$$$ and $$$m=3$$$, matrix $$$B$$$ is a valid solution, while matrix $$$C$$$ is not valid because $$$C_{1,1}+C_{2,1}=C_{1,2}+C_{1,3}$$$.

$$$$$$ B = \begin{bmatrix} 1 & 3 & 2 \\ 6 & 5 & 4 \end{bmatrix}, \quad C = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} $$$$$$

Given $$$n$$$ and $$$m$$$, can all the conditions above be satisfied? If so, output a valid solution.

$$$^{\dagger}$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is a $$$4$$$ in the array).