You are given an integer array $$$a$$$ of length $$$n$$$, where each element is an integer between $$$1$$$ and $$$10^9$$$.

For a value $$$x$$$, let $$$\text{freq}(x)$$$ denote the number of times $$$x$$$ appears in the entire array $$$a$$$.

A contiguous subarray $$$a[l \ldots r]$$$ is called complete if the following condition holds:

• For every value $$$x$$$ that appears in $$$a[l \ldots r]$$$, the number of times $$$x$$$ appears in $$$a[l \ldots r]$$$ is exactly $$$\text{freq}(x)$$$.

In other words, if a value appears in the subarray, then all of its occurrences in the whole array must be contained within that subarray.

You are given multiple test cases. For each test case, determine the total number of complete subarrays of $$$a$$$.

This is a run-twice (communication) interactive problem.

There are two players: Player A and Player B. The jury (otherwise known as the interactor of this problem) will first interact with player A. After player A ends their interaction, the jury will interact with player B. Note that player A and player B may not directly pass information to each other; both players are only able to send information to or receive information from the jury.

There is a hidden $$$n \times n$$$ grid. It contains two special points: a pile of money at $$$M = (x_M, y_M)$$$ and a bomb at $$$B = (x_B, y_B)$$$. This setup is determined by the jury before the interaction, and is consistent across both players.

Player A receives the value of $$$n$$$ and the points $$$M$$$ and $$$B$$$ from the jury. Then, Player A must send an integer $$$k$$$ ($$$1 \le k \le x$$$) back to the jury, where $$$x$$$ is the limit on $$$k$$$.

Player B receives the value of $$$n$$$ and the value of $$$k$$$ (the same integer that Player A sent) from the jury. Their task is to determine the coordinates of point $$$M$$$. To do so, Player B can make at most $$$100$$$ queries of the form $$$(x, y, d)$$$ where $$$(x, y)$$$ is a point on the grid and $$$d$$$ is a direction (up/down/left/right).

• If $$$(x, y)$$$ is in the same row or column as $$$B$$$ (i.e., $$$x = x_B$$$ or $$$y = y_B$$$ or both), then the jury will return "Boom" as the bomb explodes and burns down the money. Note that this can happen even if $$$(x, y) = M$$$, as long as $$$(x, y)$$$ is in the same row or column as $$$B$$$. Player B should give up (terminate gracefully) after a "Boom" as the money is gone.
• Otherwise, the jury will return "Yes" or "No" depending on whether the point $$$M$$$ is in $$$d$$$ direction of $$$(x, y)$$$.
  • For $$$d = U$$$ (up), $$$M$$$ is in $$$U$$$ direction of $$$(x, y)$$$ if $$$x_M \lt x$$$.
  • For $$$d = D$$$ (down), $$$M$$$ is in $$$D$$$ direction of $$$(x, y)$$$ if $$$x_M \gt x$$$.
  • For $$$d = L$$$ (left), $$$M$$$ is in $$$L$$$ direction of $$$(x, y)$$$ if $$$y_M \lt y$$$.
  • For $$$d = R$$$ (right), $$$M$$$ is in $$$R$$$ direction of $$$(x, y)$$$ if $$$y_M \gt y$$$.

Player A wants to ensure that player B can determine the coordinates of $$$M$$$. Let $$$x_{min}$$$ be the minimum value of the limit $$$x$$$ for which Player B can always do so safely, for any value $$$2 \le n \le 10^9$$$ and any valid coordinates for $$$M$$$ and $$$B$$$. Note that this value $$$x_{min}$$$ is a provable constant and is known to the jury — although you do not have to prove it (your solution only needs to respect the $$$x_{min}$$$ limit).

Your task is to act as both players and determine an optimal interaction strategy for both players so that player B determines the coordinates correctly, such that the integer $$$k$$$ follows the constraints $$$1 \le k \le x_{min}$$$.

FIRST RUN

Your code will run exactly twice on each test. On the first run, you will be Player A.

For each test case, recall you will first receive $$$n$$$ and $$$k$$$ in the input from the jury according to the input format above.

After receiving those inputs, you will be able to make at most $$$100$$$ queries of the following format: "? x y d" ($$$1 \le x, y \le n$$$ and $$$d \in \{U, D, L, R\}$$$).

After each query, the jury will respond with "Boom", "Yes", or "No" as described in the statement above. If you receive a "Boom" response in the same test case, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Once you are ready to report the coordinates of $$$M$$$, you may do so in the format: "! x y" ($$$1 \le x, y \le n$$$), where $$$(x, y)$$$ is the coordinates you wish to report.

Then, you will either proceed to the next test case, or your program must terminate if you have processed every test case. Reporting the answer does not count towards the number of queries made.

The interactor is not adaptive. That is, the points $$$M$$$ and $$$B$$$ will not change during the interaction, and will always be the same positions as shown to you in the first run.

After printing each query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded verdict.

As usual, as always, once again, Alice and Bob play a game with an array of integers. Both of them have a score of $$$0$$$ at the start of the game.

They start with an array $$$A$$$ of $$$n$$$ positive integers and play in turns. In each turn, the player must:

• Choose an element $$$x$$$ present in the current array.
• Choose an integer $$$k ~ \mathbf{(2 \leq k \leq 5)}$$$ such that $$$ x \bmod k = 0 $$$ ($$$k$$$ divides $$$x$$$). If no such $$$k$$$ exists, then the element $$$x$$$ is removed from the array and the player's score increases by 1.
• If a valid $$$k$$$ is chosen, then the number $$$x$$$ is removed from the array and is then repeatedly divided by $$$k$$$ until it is not possible to divide by $$$k$$$. The value that remains is inserted back into the array.

  Equivalently, let $$$$$$x = t \cdot k^{p}$$$$$$ where $$$p \ge 1$$$ is the largest integer such that $$$k^{p}$$$ divides $$$x$$$, and $$$t \bmod k \neq 0$$$. Then, the original $$$x$$$ is removed from the array and the number $$$t$$$ is added back to the array.

The game ends when the array becomes empty. The winner is the player with the lower score at the end. If the scores are equal, the game is considered a tie.

Alice goes first. Given the initial array $$$A$$$, determine whether Alice wins the game or not, if both the players play optimally.

You are given a tree with $$$n$$$ nodes and $$$n-1$$$ edges. Every edge $$$(u,v)$$$ has $$$w$$$ markable points. Each markable point can be marked at most once.

Each node $$$i$$$ has a permitted range $$$[l_i, r_i]$$$. Let $$$m_i$$$ denote the total number of marked points on edges incident to node $$$i$$$. For every node, the condition $$$l_i \le m_i \le r_i$$$ must hold.

You may choose any subset of nodes to supercharge. If node $$$i$$$ is supercharged:

• Its permitted range becomes $$$[2l_i, 2r_i]$$$
• The number of markable points on every edge incident to $$$i$$$ reduces by one

If both nodes at the endpoints of an edge $$$(u,v)$$$ are supercharged, then the markable points on that edge reduces by 2 (1 because of each supercharged node).

You are allowed to mark at most $$$x$$$ points in total across the entire tree.

Your task is to compute the number of valid ways (respecting the permitted ranges of all nodes) to choose supercharged nodes and marked points, modulo $$$10^9 + 7$$$.

Two ways are considered identical if and only if:

• The set of supercharged nodes is the same, and
• The set of marked points is exactly the same.

There are $$$n$$$ bags labeled $$$1$$$ to $$$n$$$. Each bag contains a set of colored coins. A color is a lowercase letter from a to z. Within a bag, no color appears more than once.

The contents of bag $$$i$$$ are denoted by the set $$$S_i$$$.

You may apply the following operation any number of times:

1. Choose an index $$$i$$$ such that $$$1 \le i \lt n$$$.
2. Replace the contents of bag $$$i$$$ by the symmetric difference of $$$S_i$$$ and $$$S_{i+1}$$$: $$$$$$ S_i \leftarrow S_i \,\Delta\, S_{i+1}, $$$$$$ while $$$S_{i+1}$$$ remains unchanged.

The symmetric difference of two sets $$$A$$$ and $$$B$$$ is $$$$$$ A \Delta B = (A \setminus B) \cup (B \setminus A). $$$$$$

For each bag, its set of colors is given as a string of distinct lowercase letters (the order does not matter).

Your task is to determine whether it is possible to transform the initial contents of all bags into their target contents.

This is an interactive problem.

There is a hidden permutation$$$^†$$$ $$$p$$$ of size $$$n$$$.

You can make queries of another permutation $$$q$$$ of size $$$n$$$. The interactor will calculate and give you $$$\sum_{i=1}^{n} p_i \oplus q_i$$$.

Using at most $$$\frac{5n}{2}$$$ queries, find the hidden permutation $$$p$$$ and output it.

$$$^†$$$An array $$$a$$$ is a permutation of size $$$n$$$ if it contains each of the elements $$$0, 1, 2, ..., n-1$$$ exactly once.

You can make queries in the following format — to query a permutation $$$q$$$, output one line of the form "? $$$q_1$$$ $$$q_2$$$ ... $$$q_n$$$" (where $$$q$$$ is a permutation of size $$$n$$$). After that, read a single integer — the value of $$$\Sigma_{i=1}^{n} p_i \oplus q_i$$$.

To report the hidden permutation as $$$q$$$, output "! $$$q_1$$$ $$$q_2$$$ ... $$$q_n$$$" (where $$$q$$$ is a permutation of size $$$n$$$). Then, the interaction continues with the next test case.

Reporting the answer does not count towards the number of queries made.

Note that you have to use the flush operation right after printing each line — otherwise you may get Idleness Limit Exceeded verdict. For example, in C++ you should use the function fflush(stdout) or cout.flush(), in Java or Kotlin — System.out.flush(), and in Python — sys.stdout.flush().

ScepticallySam owns a speed packing service that uses robots to process packages.

Each robot is assigned a pair of indices $$$i \le j$$$ and performs the following operations on a line of packages:

• stamps all packages in the subarray $$$[i, j]$$$;
• sorts the packages in $$$[i, j]$$$ in ascending order of weight.

A robot cannot move packages outside its assigned subarray.

Each line of packages is represented as an array of integers. For each line, ScepticallySam assigns robots to several non-overlapping subarrays, and all robots operate simultaneously.

After all robots finish, the entire line must be stamped and sorted in ascending order.

Given $$$t$$$ lines of packages, determine the maximum number of robots that can be assigned to each line while satisfying the above conditions.

Note: No robots were harmed in the making of this question.

You are given an array $$$a$$$ of length $$$n$$$ consisting of positive integers. You have to process $$$q$$$ queries of two types:

• 1 i g — print the number of indices $$$j$$$ ($$$j \ne i$$$) such that $$$\gcd(a_i,a_j)=g$$$;
• 2 i x — assign $$$a_i \gets x$$$ (this update affects subsequent queries).

All indices are $$$1$$$-based.

Your huge terrarium has a big glass panel. You have several stickers that you can paste onto the glass.

You have $$$n$$$ decorative stickers. For each sticker $$$i$$$ you are given:

• $$$b[i]$$$ — the beauty provided by the sticker
• $$$ir[i]$$$ — the amount of IR radiation blocked by the sticker
• $$$vis[i]$$$ — the amount of Visible Light blocked by the sticker
• $$$area[i]$$$ — the area of the sticker

You also have $$$m$$$ bottles of UV protecting cream. For each bottle $$$i$$$:

• $$$u[i]$$$ — the amount of UV radiation blocked by the bottle
• $$$au[i]$$$ — the area over which the cream must be evenly spread
• the cream can only be applied on top of decorative stickers (not on the glass directly)
• one bottle may be split across multiple stickers, but each unit area of a decorative sticker can receive cream from only one bottle
• if you choose a bottle, you must use all the cream inside it

Example clarification: If you choose bottles 1 and 2, and decorative stickers 2, 4, and 6, then the following must hold: $$$au[1] + au[2] \lt = area[2] + area[4] + area[6]$$$.

Your scientists determine the following:

• The plants will die if you block more than $$$I$$$ units of IR rays.
• The plants will die if you block more than $$$V$$$ units of Visible rays.
• The plants will die if you block less than $$$U$$$ units of UV rays.

Find the maximum total beauty you can obtain. If it is impossible to keep the plants alive, output -1.

There are $$$n$$$ types of coins with you. There are $$$c_i$$$ many coins of the $$$i^{\text{th}}$$$ type, each having value $$$v_i$$$. You are interested in knowing the smallest fraction $$$p$$$ such that $$$p$$$ fraction of the coins hold at least $$$1-p$$$ fraction of the total value of all the coins.

More formally, let $$$C = \sum_{i=1}^{n}c_i$$$ and $$$V = \sum_{i=1}^{n}c_i \cdot v_i$$$. You have to find the smallest integer $$$x$$$ such that there exists a subset of $$$x$$$ coins which have at least $$$\left(1-\frac{x}{C}\right)\cdot V$$$ value.

You have to output the integer $$$x$$$.

You are given an infinite 1-dimensional binary array of cells, which is indexed from $$$-\infty$$$ to $$$+\infty$$$. Initially, at time $$$t=0$$$, exactly $$$K$$$ distinct indices $$$P_1, P_2, \dots, P_K$$$ have the value $$$1$$$, and all other indices have the value $$$0$$$.

The array evolves over time steps $$$t=0, 1, 2, \dots$$$. The state of the array at time $$$t+1$$$ is derived from the state at time $$$t$$$ using the following rule for every index $$$i$$$:

$$$$$$ C_i^{(t+1)} = C_{i-1}^{(t)} \oplus C_{i+1}^{(t)} $$$$$$

where $$$\oplus$$$ denotes the bitwise XOR operation. (You might recognise this as elementary cellular automata on rule 90)

You must answer $$$Q$$$ queries. Each query consists of a target index $$$X$$$ and a time $$$T$$$. Determine the value of the cell at index $$$X$$$ at time $$$T$$$.

Given an array $$$a$$$ of $$$n$$$ integers and a non-negative integer $$$k$$$, find the maximum integer $$$X$$$ such that there exists at least one valid contiguous subarray $$$a[l..r]$$$ satisfying the following conditions :

• The subarray must contain at least two elements $$$(1 \le l \lt r \le n)$$$.
• Strictly more than half of the elements in the subarray must be greater than or equal to $$$X$$$.
• The cost to raise all elements in the subarray to at least $$$X$$$ must not exceed $$$k$$$ i.e. $$$\sum_{i=l}^{r} max(0, X - a_i) \le k$$$.

This is an interactive problem.

There is a hidden array $$$a$$$ of size $$$n$$$.

You can make queries of the following form:

• Provide a subset $$$P \subseteq \{1, 2, ..., n\}$$$ and a subset $$$Q \subseteq \{0, 1, 2, ..., n\}$$$.
• The interactor will construct a set $$$S = \{a_{p_i} \mid p_i \in P\} \cup Q$$$. It will calculate and give you the MEX$$$^†$$$ of the set $$$S$$$.

Using at most $$$15 n$$$ queries, find the hidden array $$$a$$$ and output it.

$$$^†$$$The MEX of a set is the smallest non-negative integer that is not present in the set. For example, MEX($$$\{0, 1, 4, 5\}$$$) is $$$2$$$ and MEX($$$\{45\}$$$) is $$$0$$$.

You can make queries in the following format — to query subsets $$$P$$$ and $$$Q$$$, output one line of the form "? $$$x$$$ $$$y$$$" (where $$$x = |P|$$$ and $$$y = |Q|$$$). On the next line, output $$$x$$$ unique space-separated integers — the elements of $$$P$$$. On the next line, output $$$y$$$ unique space-separated integers — the elements of $$$Q$$$. After that, read a single integer — the value of MEX of $$$S$$$ (which is constructed as described above).

To report the hidden array as $$$b$$$, output "! $$$b_1$$$ $$$b_2$$$ ... $$$b_n$$$". Then, the interaction continues with the next test case.

Reporting the answer does not count towards the number of queries made.

Note that you have to use the flush operation right after printing each line — otherwise you may get Idleness Limit Exceeded verdict. For example, in C++ you should use the function fflush(stdout) or cout.flush(), in Java or Kotlin — System.out.flush(), and in Python — sys.stdout.flush().

You are given a binary string $$$s$$$ of length $$$n$$$. This binary string represents an integer (without trailing zeroes) $$$x$$$.

$$$m$$$ operations are then performed on this integer. In each operation, an integer $$$k$$$ is given, and the value of $$$x$$$ is updated to $$$\lfloor x \cdot 2^{k} \rfloor$$$. Equivalently, this operation can be understood as:

• If $$$k \ge 0$$$, then $$$x$$$ is replaced by $$$x \lt \lt |k|$$$ (binary left shift by $$$k$$$ bits).
• If $$$k \lt 0$$$, then $$$x$$$ is replaced by $$$x \gt \gt |k|$$$ (binary right shift by $$$-k$$$ bits).

Output (without leading zeroes) the binary string corresponding to the final value of $$$x$$$ after all $$$m$$$ operations.